Abstract
Approximating convex bodies is a fundamental question in geometry and has a wide variety of applications. Consider 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 ε. It is known from classical results of Dudley (1974) and Bronshteyn and Ivanov (1976) that Θ((Δ/ε)^{(d1)/2}) vertices (alternatively, facets) are both necessary and sufficient. While this bound is tight in the worst case, that of Euclidean balls, 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 volume diameter Δ_d to be the diameter of a Euclidean ball of the same volume as K, and define its surface diameter Δ_{d1} analogously for surface area. It follows from generalizations of the isoperimetric inequality that Δ ≥ Δ_{d1} ≥ Δ_d.
Arya, da Fonseca, and Mount (SoCG 2012) demonstrated that the diameterbased bound could be made surfacearea sensitive, improving the above bound to O((Δ_{d1}/ε)^{(d1)/2}). In this paper, we strengthen this by proving the existence of an approximation with O((Δ_d/ε)^{(d1)/2}) facets.
This improvement is a result of the combination of a number of new ideas. As in prior work, we exploit properties of the original body and its polar dual. In order to obtain a volumesensitive bound, we explore the following more general problem. Given two convex bodies, one nested within the other, find a lowcomplexity convex polytope that is sandwiched between them. 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.
BibTeX  Entry
@InProceedings{arya_et_al:LIPIcs.SoCG.2023.9,
author = {Arya, Sunil and Mount, David M.},
title = {{Optimal VolumeSensitive Bounds for Polytope Approximation}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {9:19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772730},
ISSN = {18688969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17859},
URN = {urn:nbn:de:0030drops178592},
doi = {10.4230/LIPIcs.SoCG.2023.9},
annote = {Keywords: Approximation algorithms, convexity, Macbeath regions}
}
Keywords: 

Approximation algorithms, convexity, Macbeath regions 
Collection: 

39th International Symposium on Computational Geometry (SoCG 2023) 
Issue Date: 

2023 
Date of publication: 

09.06.2023 