On the combinatorial complexity of approximating polytopes

DOI10.1007/S00454-016-9856-5MaRDI QIDQ1688856zbMATH OpenOpenAlexWikidataFDO

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

Publication date 11 January 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial complexityconvex polytopesmacbeath regionspolytope approximation

Mathematics Subject Classification ID

Approximation by convex sets (52A27) Combinatorial complexity of geometric structures (52C45)

Abstract: Approximating convex bodies succinctly by convex polytopes is a fundamental problem in discrete geometry. A convex body $K$ of diameter $mathrmdiam(K)$ is given in Euclidean $d$-dimensional space, where $d$ is a constant. Given an error parameter $varepsilon>0$, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from $K$ is at most $varepsiloncdotmathrmdiam(K)$. By combinatorial complexity we mean the total number of faces of all dimensions of the polytope. A well-known result by Dudley implies that $O(1/varepsilo{n}^{(d-1)/2})$ facets suffice, and a dual result by Bronshteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating polytope whose total combinatorial complexity is $ildeO(1/varepsilo{n}^{(d-1)/2})$, where $ildeO$ conceals a polylogarithmic factor in $1/varepsilon$. This is a significant improvement upon the best known bound, which is roughly $O(1/varepsilo{n}^{d-2})$. Our result is based on a novel combination of both old and new ideas. First, we employ Macbeath regions, a classical structure from the theory of convexity. The construction of our approximating polytope employs a new stratified placement of these regions. Second, in order to analyze the combinatorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of B'{a}r'{a}ny and Larman's economical cap covering. Finally, we use a deterministic adaptation of the witness-collector technique (developed recently by Devillers et al.) in the context of our stratified construction.

Recommendations

• On the combinatorial complexity of approximating polytopes
• Optimal area-sensitive bounds for polytope approximation
• Polytope approximation and the Mahler volume
• Fine approximation of convex bodies by polytopes
• scientific article; zbMATH DE number 665688

Cites work

• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• A theorem on non-homogeneous lattices
• Algorithms for polytope covering and approximation
• Approximate polytope membership queries
• Approximating extent measures of points.
• Approximation by polygons and polyhedra
• Approximation of convex sets by polytopes
• Approximation of general smooth convex bodies
• Asymptotic estimates for best and stepwise approximation of convex bodies II
• Building triangulations using \({\epsilon}\)-nets
• Complexity analysis of random geometric structures made simpler
• Convex bodies, economic cap coverings, random polytopes
• Geometric approximation algorithms
• How hard is half-space range searching?
• scientific article; zbMATH DE number 5302813 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• Intrinsic volumes and f-vectors of random polytopes
• Metric entropy of some classes of sets with differentiable boundaries
• Optimal area-sensitive bounds for polytope approximation
• Polyhedral approximation of smooth convex bodies
• Separation and approximation of polyhedral objects
• The approximation of convex sets by polyhedra
• The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
• The effect of corners on the complexity of approximate range searching
• The maximum numbers of faces of a convex polytope
• The technique of \(M\)-regions and cap coverings: A survey
• Tight lower bounds for halfspace range searching

Cited in

(26)

• On the complexity of approximating the maximal inscribed ellipsoid for a polytope
• On the complexity of polytope isomorphism problems
• Oracle-polynomial-time approximation of largest simplices in convex bodies
• On affine reducibility of combinatorial polytopes
• Strong IP formulations need large coefficients
• Covering convex bodies and the closest vector problem
• Complexity yardsticks for \(f\)-vectors of polytopes and spheres
• Multiobjective optimization under uncertainty: a multiobjective robust (relative) regret approach
• Approximating a planar convex set using a sparse grid
• Optimal area-sensitive bounds for polytope approximation
• Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes
• On the combinatorial complexity of approximating polytopes
• On the polytope faces of the graph approximation problem
• scientific article; zbMATH DE number 5598224 (Why is no real title available?)
• Approximate convex intersection detection with applications to width and Minkowski sums
• Economical Delone sets for approximating convex bodies
• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• scientific article; zbMATH DE number 5592483 (Why is no real title available?)
• Polytope approximation and the Mahler volume
• Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
• Economical convex coverings and applications
• Optimal volume-sensitive bounds for polytope approximation
• Delaunay triangulations in the Hilbert metric
• Approximate nearest-neighbor search for line segments
• Optimal area-sensitive bounds for polytope approximation
• Farthest-point Voronoi diagrams in the Hilbert metric

This page was built for publication: 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 Q1688856)