On the combinatorial complexity of approximating polytopes

DOI10.1007/s00454-016-9856-5zbMath1381.52031arXiv1604.01175OpenAlexW2963756047WikidataQ59545298 ScholiaQ59545298MaRDI QIDQ1688856

Sunil Arya, David M. Mount, Guilherme Dias 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 polytopespolytope approximationmacbeath regions

Mathematics Subject Classification ID

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

Related Items

Covering convex bodies and the closest vector problem ⋮ Unnamed Item ⋮ Multiobjective optimization under uncertainty: a multiobjective robust (relative) regret approach ⋮ Strong IP formulations need large coefficients ⋮ Approximating a planar convex set using a sparse grid ⋮ Economical Delone Sets for Approximating Convex Bodies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight lower bounds for halfspace range searching
• How hard is half-space range searching?
• Intrinsic volumes and f-vectors of random polytopes
• The effect of corners on the complexity of approximate range searching
• Polyhedral approximation of smooth convex bodies
• The approximation of convex sets by polyhedra
• Approximation of general smooth convex bodies
• Separation and approximation of polyhedral objects
• Metric entropy of some classes of sets with differentiable boundaries
• Approximation of convex sets by polytopes
• A theorem on non-homogeneous lattices
• Optimal area-sensitive bounds for polytope approximation
• Building triangulations using ε-nets
• Approximating extent measures of points
• Convex bodies, economic cap coverings, random polytopes
• Asymptotic estimates for best and stepwise approximation of convex bodies II
• Algorithms for polytope covering and approximation
• Complexity analysis of random geometric structures made simpler
• Approximate polytope membership queries
• The directions of the line segments and of the r ‐dimensional balls on the boundary of a convex body in Euclidean space
• The maximum numbers of faces of a convex polytope
• A Lower Bound for the Volume of Strictly Convex Bodies with many Boundary Lattice Points
• Approximation by polygons and polyhedra