Optimal area-sensitive bounds for polytope approximation
Sunil Arya, Guilherme Dias da Fonseca, David M. Mount · 2012
Approximating convex bodies is a fundamental question in geometry and has applications to a wide variety of optimization problems. Given a convex body K in REd for fixed d, the objective is to minimize the number of vertices or facets of an approximating polytope for a given Hausdorff error ε. The best known uniform bound, due to Dudley (1974), shows that O((diam(K)/ε)(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. 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(√area(K)/ε(d-1)/2) facets, where area(K) is the surface area of the body. This bound is never worse than the previous bound and may be significantly better for skinny bodies. This bound is provably optimal in the worst case and improves upon our earlier result (which appeared in SODA 2012).