Running summarizing tools on a new article
Check the paper below, then start its synthesis.
Optimal Volume-Sensitive Bounds for Polytope Approximation
Sunil Arya (Hong Kong University of Science and Technology), David M. Mount (University of Maryland, College Park)
Abstract: Abstract Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body K in $$\mathbb {R}^d$$ R d for fixed d , the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error $$\varepsilon $$ ε . It is known that $$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})$$ 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 $$\Delta _d(K)$$ Δ d ( K ) is defined to be the diameter of a Euclidean ball of the same volume as K . The surface diameter $$\Delta _{d-1}(K)$$ Δ d - 1 ( K ) is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that $${{\,\textrm{diam}\,}}(K) \ge \Delta _{d-1}(K) \ge \Delta _d(K)$$ 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((\Delta _{d-1}(K)/\varepsilon )^{(d-1)/2})$$ O ( ( Δ d - 1 ( K ) / ε ) ( d - 1 )