Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.09586 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909998193311744 |
|---|---|
| author | Arya, Sunil Mount, David M. |
| author_facet | Arya, Sunil Mount, David M. |
| contents | Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body $K$ in $\textbf{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((\text{diam}(K)/\varepsilon)^{(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 \emph{volume diameter} $Δ_d(K)$ is defined to be the diameter of a Euclidean ball of the same volume as $K$. The \emph{surface diameter} $Δ_{d-1}(K)$ is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that $\text{diam}(K) \geq Δ_{d-1}(K) \geq Δ_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)/\varepsilon)^{(d-1)/2})$. In this paper, we strengthen this by proving the existence of an approximation with $O((Δ_d(K)/\varepsilon)^{(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_09586 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal Volume-Sensitive Bounds for Polytope Approximation Arya, Sunil Mount, David M. Computational Geometry Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body $K$ in $\textbf{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((\text{diam}(K)/\varepsilon)^{(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 \emph{volume diameter} $Δ_d(K)$ is defined to be the diameter of a Euclidean ball of the same volume as $K$. The \emph{surface diameter} $Δ_{d-1}(K)$ is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that $\text{diam}(K) \geq Δ_{d-1}(K) \geq Δ_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)/\varepsilon)^{(d-1)/2})$. In this paper, we strengthen this by proving the existence of an approximation with $O((Δ_d(K)/\varepsilon)^{(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. |
| title | Optimal Volume-Sensitive Bounds for Polytope Approximation |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2303.09586 |