.png){kind=icon}
.png){kind=icon}
Return
Optimal Volume-Sensitive Bounds for Polytope Approximation
.png){kind=icon}
OA
AI
DOI：10.1007/s00454-025-00780-z.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body K in Rd\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}<^>d$$\end{document} for fixed d, the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}. It is known that O((diam(K)/epsilon)(d-1)/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(({{\,\textrm{diam}\,}}(K)/\varepsilon )<^>{(d-1)/2})$$\end{document} 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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _d(K)$$\end{document} is defined to be the diameter of a Euclidean ball of the same volume as K. The surface diameter Delta d-1(K)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta _{d-1}(K)$$\end{document} is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that diam(K)>=Delta d-1(K)>=Delta d(K)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{diam}\,}}(K) \ge \Delta _{d-1}(K) \ge \Delta _d(K)$$\end{document}. 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)/epsilon)(d-1)/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((\Delta _{d-1}(K)/\varepsilon )<^>{(d-1)/2})$$\end{document}. In this paper, we strengthen this by proving the existence of an approximation with O((Delta d(K)/epsilon)(d-1)/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((\Delta _d(K)/\varepsilon )<^>{(d-1)/2})$$\end{document} 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.
Keywords:
Convex approximation
Macbeath regions
Polarity
Mahler volume
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
D
IF:
0.6
Papers:
14
Citations:
2.6K
Organization
No organization information available