Optimal Area-Sensitive Bounds for Polytope Approximation
share
Approximating convex bodies is a fundamental question in geometry and has a wide variety of applications. Given a convex body K of diameter Δ in ℝ^d for fixed d, the objective is to minimize the number of vertices (alternatively, the number of facets) of an approximating polytope for a given Hausdorff error ε. The best known uniform bound, due to Dudley (1974), shows that O((Δ/ε)^(d-1)/2) facets suffice. While this bound is optimal in the case of a Euclidean ball, it is far from optimal for “skinny” convex bodies. A natural way to characterize a convex object's skinniness is in terms of its relationship to the Euclidean ball. Given a convex body K, define its surface diameter Δ_d-1 to be the diameter of a Euclidean ball of the same surface area as K. It follows from generalizations of the isoperimetric inequality that Δ≥Δ_d-1. We show that, under the assumption that the width of the body in any direction is at least ε, it is possible to approximate a convex body using O((Δ_d-1/ε)^(d-1)/2) facets. This bound is never worse than the previous bound and may be significantly better for skinny bodies. The bound is tight, in the sense that for any value of Δ_d-1, there exist convex bodies that, up to constant factors, require this many facets. The improvement arises from a novel approach to sampling points on the boundary of a convex body. We employ a classical concept from convexity, called Macbeath regions. We demonstrate that Macbeath regions in K and K's polar behave much like polar pairs. We then apply known results on the Mahler volume to bound their number.
READ FULL TEXT