Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the question of how to succinctly approximate a multidimensional convex body by a polytope. We are given a convex body K of unit diameter in Euclidean d-dimensional space (where d is a constant) along with an error parameter \varepsilon > 0. The objective is to determine a  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 of the polytope. In the mid-1970's, a result by Dudley showed that O(1/\varepsilon^{(d-1)/2}) facets suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices . While both results match known worst-case lower bounds , obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound. In this paper, we settle this problem with an asymptotically optimal bound of O(1/\varepsilon^{(d-1)/2})  . Our result is based on a new relationship between \varepsilon-width caps of a convex body and its polar  . 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  result by combining this with a variant of the witness-collector method and a novel variable-width layered construction .
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 .
R
Convex bodies play a fundamental role in geometric computation, and approximating such bodies is often a key ingredient in the design of efficient algorithms. We consider the
This paper considers the
R
We are given
Given
R
along with
and
R
0. The
0, the
A
convex
R
combinatorial complexity
combinatorial complexity
R
of the polytope. In the mid-1970's, a result by Dudley showed
. Classical constructions by Dudley and Bronshteyn/Ivanov show
R
suffice, and Bronshteyn and Ivanov presented a similar bound on the number of vertices . While both results match known worst-case lower bounds , obtaining a similar upper bound on the total combinatorial complexity has been open for over 40 years. Recently, we made a first step forward towards this objective, obtaining a suboptimal bound.
or vertices are possible, respectively, but neither achieves both bounds simultaneously.
R
settle this problem with an asymptotically optimal bound of
show that it is possible to construct a polytope with
A
combinatorial complexity, which is optimal in the worst case
A
body
A
main
R
variable-width layered construction
variable-thickness layered construction of the economical cap covering