Ju Sun (孙举)

Dedicated to my research and life

Simplicial Covering of Vertices of Random Polytopes

| Comments

Sample \(n\) points \(\left\{\mathbf x_1, \cdots, \mathbf x_n\right\}\) i.i.d. uniform from the unit sphere \(\mathbb S^{d-1}\) and consider the convex polytope formed as \(\mathcal K = \operatorname{\mathbf{conv}}\left(\mathbf x_1, \cdots, \mathbf x_n\right)\). With probability one, the polytope is simplicial, which means each facet is exactly a \(d-1\) simplex and there is no other points lying in it.

There are many questions of probabilistic and combinatorial nature that can be posed for this setting. Recent research on this culminates in proving some concentration results to the \(\mathrm{volume}\left(\mathcal K\right)\) in this paper1. In fact, the result applies to points sampled i.i.d. uniform from the boundary of any convex body with smooth boundaries:

Theorem 1 For any compact convex body \(\mathbf K\) with nonempty interior and \(\mathcal C^2\) boundaries and everywhere positive Gauss-Kronecker curvature, there are positive constants \(\alpha\) and \(c\) such that the following holds: consider the convex polytope \(\mathcal K_n = \operatorname{\mathbf{conv}}\left(\mathbf x_1, \cdots, \mathbf x_n\right)\), where \(x_i\)’s are sampled i.i.d. uniform from the boundary of \(\mathbf K\). For any constant \(0 < \eta < \frac{d-1}{3d+1}\) and \(0 < \lambda \leq \frac{\alpha}{4} n^{\left(d-1\right)/\left(3d+1\right) + 2\left(d+1\right)\eta/\left(d-1\right)}\), we have \[\begin{align} \mathbb P\left[\left|\mathrm{Vol}\left(\mathcal K_n\right)- \mathbb E\mathrm{Vol}\left(\mathcal K_n\right) \right| > \sqrt{\lambda V_0}\right] \leq 2\exp\left(-\lambda/4\right) + \exp\left(-cn^{\left(d-1\right)/\left(3d+1\right) - \eta}\right) \end{align}\] where \(V_0 = \alpha n^{-\left(d+3\right)/\left(d-1\right)}\).

This development is in line with the more developed results that achieves central limit theorems (CLT) of various quantities of interest for the model in which random points sampled directly from the mother convex body \(\mathbf K\), instead of its boundary. See this paper2.

One problem from my research project recently is more leaned toward the combinatorial side. A simple version is like this: consider \(\mathcal K\) as in the first paragraph, how many facets one needs to randomly color (say in red), such that ultimately 1) the colored regions are connected; and 2) any vertex lie in at least colored facet. Here by “randomly” we mean uniform as measured by the “volume of the spherical simplex” subtended by facets, normalized by the surface area of \(\mathbb S^{d-1}\) of course. It is very easy to see the lower bound is \[\begin{align*} \Omega\left(n/d\right) \end{align*}\] as this is the least required if one were to cover all vertices. It is not immediately clear what the upper bound is. Intuitively, since the random polytopes tend to behave like very “regular objects”, and our sampling is “uniformly” random, one expects substantially fewer such colored facets to cover all vertices, rather than all facets, the number of which is often exponential in \(d\). Some simulations (of course, computation quickly becomes prohibitive even one’s interested in computing the convex hull of many points in large dimensions) suggest the upper bound is at most \[\begin{align} O\left(n\log n\right), \end{align}\] which is very mild as compared to the crude estimate of the number of facets one’d have \[\begin{align} \binom{n}{d} \leq \frac{n^d}{d!}. \end{align}\]

  1. An Inscribing Model for Random Polytopes, by Richardson, Vu, and Wu, http://link.springer.com/article/10.1007%2Fs00454-007-9012-3

  2. Sharp Concentration of Random Polytopes, by Vu, http://link.springer.com/article/10.1007%2Fs00039-005-0541-8