Optimal Area-Sensitive Bounds for Polytope Approximation

Abstract Approximating convex bodies is a fundamental problem in geometry. Given a convex body K in $$\mathbb {R}^d$$ R d for a fixed dimension d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ ε . The best known uniform bound, due to Dudley (1974), shows that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( diam ( K ) / ε ) ( d - 1 ) / 2 ) facets suffice. Although this bound is optimal for fat objects, such as Euclidean balls, it is far from optimal for “skinny” convex bodies. Skinniness can be characterized relative to the Euclidean ball. Given a convex body K , define its area radius , $${{\,\textrm{arad}\,}}(K)$$ arad ( K ) , to be the radius of the Euclidean ball having the same surface area as K . It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge 2 \cdot {{\,\textrm{arad}\,}}(K)$$ diam ( K ) ≥ 2 · arad ( K ) . We show that, given a convex body whose minimum width is at least $$\varepsilon $$ ε , it is possible to approximate the body by a polytope having $$O(({{\,\textrm{arad}\,}}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( arad ( K ) / ε ) ( d - 1 ) / 2 ) facets. Our approach works by first reducing the problem of approximating convex bodies to that of approximating convex functions. We employ a classical concept from convexity, called Macbeath regions. We demonstrate that there is a polar relationship between the Macbeath regions of a function and the Macbeath regions of its Legendre dual. This is combined with known bounds on the Mahler volume to bound the total size of the approximation.