  Approximating convex bodies succinctly by convex polytopes is a fundamental
problem in discrete geometry. A convex body $K$ of diameter $\mathrm{diam}(K)$
is given in Euclidean $d$-dimensional space, where $d$ is a constant. Given an
error parameter $\varepsilon > 0$, the objective is to determine a polytope of
minimum combinatorial complexity whose Hausdorff distance from $K$ is at most
$\varepsilon \cdot \mathrm{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/\varepsilon^{(d-1)/2})$ facets suffice, and a dual
result by Bronshteyn and Ivanov similarly bounds the number of vertices, but
neither result bounds the total combinatorial complexity. We show that there
exists an approximating polytope whose total combinatorial complexity is
$\tilde{O}(1/\varepsilon^{(d-1)/2})$, where $\tilde{O}$ conceals a
polylogarithmic factor in $1/\varepsilon$. This is a significant improvement
upon the best known bound, which is roughly $O(1/\varepsilon^{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 combinatorial
complexity of the approximating polytope, we present a tight analysis of a
width-based variant of B\'{a}r\'{a}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.
