On the combinatorial complexity of approximating polytopes
From MaRDI portal
Publication:1688856
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
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