Random approximation and the vertex index of convex bodies

Abstract

We prove that there exists an absolute constant $\alpha >1$ with the following property: if $K$ is a convex body in ${\mathbb{R}}^n$ whose center of mass is at the origin, then a random subset $X\subset K$ of cardinality $\mathrm{card}(X)=\lceil \alpha n\rceil$ satisfies with probability greater than $1-e^{-n}$ {K\subseteq c_1n\,{\mathrm conv}(X),} where $c_1>0$ is an absolute constant. As an application we show that the vertex index of any convex body $K$ in ${\mathbb{R}}^n$ is bounded by $c_2{n}^2$, where $c_2>0$ is an absolute constant, thus extending an estimate of Bezdek and Litvak for the symmetric case.