The problem of approximating a convex body by convex polytopes is of great importance both from a theoretical and from an algorithmic point of view. The present paper surveys the main results in this field, discusses underlying ideas and techniques (mainly from differential geometry, number theory and the theory of algorithms) and indicates connections to various other problems. Detailed outlines of proofs are given for selected recent results.
After the introduction, asymptotic results (as the number of vertices or facets of the approximating polytopes tend to infinity) on best approximation of plane convex bodies are presented for various common metrics – in particular, recent asymptotic formula of M. Ludwig are discussed in more detail. Section 3 deals with asymptotic best approximation in arbitrary dimensions with emphasis on interesting new results of Schneider, Glasauer and the author. Section 4 delineates the algorithmic situation, particularly with respect to stepwise approximation. The goal is to find efficient algorithms that produce “well-approximating” polytopes within specified classes of polytopes (like those with a given number of vertices or facets). Section 5 contains various other approximation results and supplements the author’s earlier survey [Handbook of convex geometry. Vol. A, 319-345 (1993; Zbl 0791.52007)].
For the entire collection see [Zbl 0797.00016].