Random volumes in d-dimensional polytopes

Random volumes in d-dimensional polytopes, Discrete Analysis 2020:15, 17 pp.

This paper concerns the following general question. Given a convex body $X$ in $\mathbb R^d$, how many points do you need to choose at random from inside $X$ before with high probability their convex hull approximates $X$? More precisely, given $\epsilon>0$, how large does $N$ need to be to guarantee that the volume of the convex hull of $N$ random points in $X$ is with high probability at least $1-\epsilon$ times the volume of $X$? (More precisely still, we take a sequence of convex bodies $X_d\subset\mathbb R^d$ with $d\to\infty$ and would like the probability in question to be $1-o(1)$.)

If $X$ is a unit sphere, the answer is known to be of order $d^{d/2}$. The rough reason it needs to be superexponential is that with only exponentially many points, the best one can hope for is a very well spread out set $\Gamma$ of exponentially many points close to the boundary. However, the typical distance of a point on the boundary from a point in $\Gamma$ will be some positive constant (depending on the exponent), so almost all of the convex hull will be contained in a sphere of radius $(1-\delta)$ for some $\delta>0$, which has volume $(1-\delta)^d|X|$. To look at it another way, we need $\delta$ to be small compared with $d^{-1}$. For that we would like a $d^{-1/2}$-net of points very near the boundary (the square root comes from the fact that $\cos(\delta^{1/2})\approx 1-\delta/2$), and such a net has to have size at least $(Cd^{1/2})^d$.

Another known example is when $X$ is a cube. Here one can exploit the fact that the coordinates of a random point in $X$ are independent, which makes a number of calculations easier. It turns out that for the cube, exponentially many points suffice. In fact, even the right exponent is known.

This paper looks at the case of simplicial polytopes with few faces. Since a point in the middle of such a polytope can be joined to all the simplicial facets to decompose the polytope into simplices, the problem reduces straightforwardly to the question where the polytope is in fact a simplex.

It is slightly tricky to get an intuitive feel for what the right answer should be in this case. One might at first think that it was important for the random points to include points very close to the vertices of the simplex, but that is not necessary, since we are not aiming to find just $d+1$ points whose convex hull approximates the simplex. Furthermore, only an exponentially small part of the measure of the simplex is close to the corners, so in a sense we do not care about those points. So there are different factors at play that seem to work in different directions: the corners are hard to get close to, but for that very reason they do not matter too much, but on the other hand points near corners are very useful for making convex combinations.

Very roughly what the authors do is identify a subset of the simplex that contains almost all the measure and prove that each point $x$ in that subset is almost certainly contained in the convex hull. Then by Markov’s inequality, with high probability most points of the subset are in the convex hull. To prove that suitable points $x$ are very likely to belong to the convex hull, they cut off a “cap” near each vertex that is large enough to be exponentially (as opposed to super-exponentially) small. With high probability each cap will contain many points from the random set, which is a promising start, but the bulk of the work in the paper consists in showing, by means of ingenious arguments, that there will be many points in the caps that are related to $x$ in a suitable way that makes it highly likely that $x$ belongs to their convex hull.