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

convex polytopescombinatorial complexitypolytope approximationmacbeath regions

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

• scientific article; zbMATH DE number 5302813 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• 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?
• 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

(21)

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

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)