2023/03/16 by Arya, Sunil, Mount, David M.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2303.09586
Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body K in Rd for fixed d, the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error ε. It is known that O((diam(K)/ε)(d-1)/2) facets suffice and are necessary for many instances, such as the Euclidean ball. However, this bound is far from optimal for ``skinny'' convex bodies. A natural way to characterize the skinniness of a convex object is in terms of its relationship to the Euclidean ball. Given a convex body K, its volume diameter Δd(K) is defined to be the diameter of a Euclidean ball of the same volume as K. The surface diameter Δd-1(K) is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that diam(K) ≥ Δd-1(K) ≥ Δd(K). Arya, da Fonseca, and Mount proved that the diameter-based bound could be made sensitive to the surface diameter, improving the above bound to O((Δd-1(K)/ε)(d-1)/2). In this paper, we strengthen this by proving the existence of an approximation with O((Δd(K)/ε)(d-1)/2) facets. As a function of volume alone, this bound is tight up to constant factors. Our improvements arise from a combination of new ideas. We exploit known properties of the original body and its polar dual. In order to obtain a volume-sensitive bound, we explore the problem of computing a low-complexity polytope that is sandwiched between two given convex bodies. We show that this problem can be reduced to a covering problem involving a natural intermediate body based on the harmonic mean. Our proof relies on a geometric analysis of a relative notion of fatness involving these bodies.