Approximating convex bodies succinctly by convex polytopes is a funda-mental problem in discrete geometry. A convex body K of diameter diam(K ) is given in Euclidean d-dimensional space, where d is a constant. Given an error parameter ε > 0, the objective is to determine a polytope of minimum combinatorial complexity whose Hausdorff distance from K is at most ε·diam(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/ε (d−1)/2 ) facets suffice, and a dual result by Bron-shteyn and Ivanov similarly bounds the number of vertices, but neither result bounds the total combinatorial complexity. We show that there exists an approximating poly-tope whose total combinatorial complexity is (d−1)/2 ), where O conceals apolylogarithmic factor in 1/ε. This is a significant improvement upon the best known bound, which is roughly O(1/ε 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 combi-natorial complexity of the approximating polytope, we present a tight analysis of a width-based variant of Bárá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.

EB00000003734K

Available