# Optimal Bound on the Combinatorial Complexity of Approximating Polytopes

arXiv: https://arxiv.org/abs/1910.14459 · HTML: https://mlsanity.com/paper/1910.14459/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2019.

## Built on by (most cited first, 2 of 2)

- [Uniform Brackets, Containers, and Combinatorial Macbeath Regions](https://mlsanity.com/paper/2111.10048/) (2021)
- [Learning efficient representations of complex constraints for scalable optimization](https://mlsanity.com/paper/2603.08283/) (2026)

## Abstract (arXiv)

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/varepsilon(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/varepsilon(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.