.png){kind=icon}
.png){kind=icon}
Return
Optimal Area-Sensitive Bounds for Polytope Approximation
.png){kind=icon}
OA
AI
DOI：10.1007/s00454-025-00815-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Approximating convex bodies is a fundamental problem in geometry. 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 a fixed dimension 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}. The best known uniform bound, due to Dudley (1974), shows 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. Although this bound is optimal for fat objects, such as Euclidean balls, it is far from optimal for skinny convex bodies. Skinniness can be characterized relative to the Euclidean ball. Given a convex body K, define its area radius, arad(K)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{arad}\,}}(K)$$\end{document}, to be the radius of the Euclidean ball having the same surface area as K. It follows from generalizations of the isoperimetric inequality that diam(K)>= 2arad(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 2 \cdot {{\,\textrm{arad}\,}}(K)$$\end{document}. We show that, given a convex body whose minimum width is at least 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 possible to approximate the body by a polytope having O((arad(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{arad}\,}}(K)/\varepsilon )<^>{(d-1)/2})$$\end{document} facets. Our approach works by first reducing the problem of approximating convex bodies to that of approximating convex functions. We employ a classical concept from convexity, called Macbeath regions. We demonstrate that there is a polar relationship between the Macbeath regions of a function and the Macbeath regions of its Legendre dual. This is combined with known bounds on the Mahler volume to bound the total size of the approximation.
Keywords:
Convex approximation
Convex-function approximation
Dual conjugate
Mahler volume . Macbeath regions
Journal
D
IF:
0.6
Papers:
62
Citations:
0
Organization
View more organizations