Approximation of smooth convex bodies by random polytopes

Abstract

Let $K$ be a convex body in ${\mathbb{R}}^n$ and $f:\partial K\to {\mathbb{R}}_{+}$ a continuous, strictly positive function with $\underset{\partial K}{\int }f(x)d{\mu }_{\partial K}(x)=1$. We give an upper bound for the approximation of $K$ in the symmetric difference metric by an arbitrarily positioned polytope $P_f$ in ${\mathbb{R}}^n$ having a fixed number of vertices. This generalizes a result by Ludwig, Schütt and Werner $[36]$. The polytope $P_f$ is obtained by a random construction via a probability measure with density $f$. In our result, the dependence on the number of vertices is optimal. With the optimal density $f$, the dependence on $K$ in our result is also optimal.