Optimal Bound on the Combinatorial Complexity of Approximating Polytopes

DOI10.1145/3559106MaRDI QIDQ6058263zbMATH OpenOpenAlexFDO

Authors Rahul Arya, Sunil Arya, Guilherme D. Da Fonseca, David M. Mount

Publication date 31 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.14459

zbMATH Keywords

convex polytopesmacbeath regionspolytope approximation

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: This paper considers the question of how to succinctly approximate a multidimensional convex body by a polytope. Given a convex body $K$ of unit diameter in Euclidean $d$-dimensional space (where $d$ is a constant) and an error parameter $varepsilon>0$, the objective is to determine a convex polytope of low combinatorial complexity whose Hausdorff distance from $K$ is at most $varepsilon$. By combinatorial complexity we mean the total number of faces of all dimensions. Classical constructions by Dudley and Bronshteyn/Ivanov show that $O(1/varepsilo{n}^{(d-1)/2})$ facets or vertices are possible, respectively, but neither achieves both bounds simultaneously. In this paper, we show that it is possible to construct a polytope with $O(1/varepsilo{n}^{(d-1)/2})$ combinatorial complexity, which is optimal in the worst case. Our result is based on a new relationship between $varepsilon$-width caps of a convex body and its polar body. Using this relationship, we are able to obtain a volume-sensitive bound on the number of approximating caps that are "essentially different." We achieve our main result by combining this with a variant of the witness-collector method and a novel variable-thickness layered construction of the economical cap covering.

Recommendations

• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• On the combinatorial complexity of approximating polytopes
• On the combinatorial complexity of approximating polytopes
• Optimal volume-sensitive bounds for polytope approximation
• Optimal area-sensitive bounds for polytope approximation

Cited in

(14)

• On the complexity of approximating the maximal inscribed ellipsoid for a polytope
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
• On the polytope faces of the graph approximation problem
• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• Economical convex coverings and applications
• Optimal volume-sensitive bounds for polytope approximation
• Optimal volume-sensitive bounds for polytope approximation
• An efficient algorithm for vertex enumeration of arrangement
• Delaunay triangulations in the Hilbert metric
• Ipelets for the convex polygonal geometry (media exposition)
• Optimal area-sensitive bounds for polytope approximation
• Farthest-point Voronoi diagrams in the Hilbert metric

This page was built for publication: Optimal Bound on the Combinatorial Complexity of Approximating Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6058263)