The combinatorial structure of random polytopes (Q705993): Difference between revisions

Choose \(n\) random points in \(\mathbb R^d\) identically, independently and according to a given density function. Their convex hull is a polytope \(P_n\). The combinatorial structure of the polytope \(P_n\) is described by the \(f\)-vector of \(P_n\), where \(f(P_n) = (f_0(P_n),\dots , f_{d-1}(P_n))\), and \(f_i(P_n)\) is the number of \(i\)-dimensional faces of \(P_n\). It is one of the classical problems in geometric probability and stochastic geometry to investigate the combinatorial structure of random convex hulls [see the survey article: \textit{R. Schneider}, `Discrete aspects of stochastic geometry', Handbook of Discrete and Computational Geometry, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, 2nd edition (2004)]. In general, the problem to determine the expectation of \(f(P_n)\) turns out to be difficult. Only the number of vertices \(Ef_0(P_n)\) and facets \(Ef_{d-1}(P_n)\) have been investigated (\(E\) stands for expectation). The only case where all entries of the \(f\)-vector are known in arbitrary dimensions is the case of convex hulls of standard normal random variables: \(Ef_i(P_n) = c(d,i)\, (\ln n)^{(d-1)/2} + o((\ln n)^{(d-1)/2})\) [see: \textit{F. Affentranger} and \textit{R. Schneider}, Discrete Comput. Geom. 7, 219--226 (1992; Zbl 0751.52002)]. In this paper, the author presents a general method to determine the expectation of the \(f\)-vector of random polytopes chosen in a smooth convex body or in a polytope. The main results of the paper are the following two results. Theorem. Let \(K\) be a convex body and \(n\) points chosen in \(K\) independently and according to the uniform distribution. Then I) if \(K\) is a polytope, then \(Ef(P_n)\,(\ln n)^{-(d-1)} \to \overline{c}_d\, T(K)\), as \(n\to\infty\), where \(T(K)\) denotes the number of towers of \(K\), and \(\overline {c}_d\) is a constant vector in \(\mathbb R^d\); II) if \(K\) is of differentiability class \(\mathbb E^2\) with positive Gaussian curvature, then \(Ef(P_n)\, n^{(1-d)/(d+1)}\to c_d\, \Omega(K)\) in probability as \(n\to\infty\), where \(\Omega(K)\) is the affine surface area of \(K\), and \(c_d\) is a constant vector in \(\mathbb R^d\). These results imply an extremal property for random points chosen in a simplex. See, also Theorem 3, Theorem 4, and the discussion after formula (6.3) in the paper: \textit{I. Bárány} and \textit{C. Buchta} [Math. Ann. 297, No. 3, 467--497 (1993; Zbl 0788.52003)].