The monotonicity of f-vectors of random polytopes

Olivier Devillers (INRIA)
Marc Glisse (INRIA)
Xavier Goaoc (INRIA)
Guillaume Moroz (INRIA)
Matthias Reitzner (Universität Osnabrück.)


Let $K$ be a compact convex body in ${\mathbb R}^d$, let $K_n$ be the convex hull of $n$ points chosen uniformly and independently in $K$, and let $f_{i}(K_n)$ denote the number of $i$-dimensional faces of $K_n$. We show that for planar convex sets, $E[f_0 (K_n)]$ is increasing in $n$.  In dimension $d \geq 3$ we prove that if $\lim_{n \to \infty} \frac{E[f_{d-1}(K_n)]}{An^c}=1$ for some constants $A$ and $c>0$ then the function $n \mapsto E[f_{d-1}(K_n)]$ is increasing for $n$ large enough. In particular, the number of facets of the convex hull of $n$ random points distributed uniformly and independently in a smooth compact convex body is asymptotically increasing. Our proof relies on a random sampling argument.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-8

Publication Date: March 28, 2013

DOI: 10.1214/ECP.v18-2469


  • Bárány, I.; Larman, D. G. Convex bodies, economic cap coverings, random polytopes. Mathematika 35 (1988), no. 2, 274--291. MR0986636
  • Buchta, Christian; Reitzner, Matthias. Equiaffine inner parallel curves of a plane convex body and the convex hulls of randomly chosen points. Probab. Theory Related Fields 108 (1997), no. 3, 385--415. MR1465165
  • Chazelle, Bernard. The discrepancy method. Randomness and complexity. Cambridge University Press, Cambridge, 2000. xviii+463 pp. ISBN: 0-521-77093-9 MR1779341
  • Clarkson, Kenneth L. New applications of random sampling in computational geometry. Discrete Comput. Geom. 2 (1987), no. 2, 195--222. MR0884226
  • Clarkson, Kenneth L.; Shor, Peter W. Applications of random sampling in computational geometry. II. Discrete Comput. Geom. 4 (1989), no. 5, 387--421. MR1014736
  • Dafnis, N.; Giannopoulos, A.; Guédon, O. On the isotropic constant of random polytopes. Adv. Geom. 10 (2010), no. 2, 311--322. MR2629817
  • Edelsbrunner, Herbert. Algorithms in combinatorial geometry. EATCS Monographs on Theoretical Computer Science, 10. Springer-Verlag, Berlin, 1987. xvi+423 pp. ISBN: 3-540-13722-X MR0904271
  • Efron, Bradley. The convex hull of a random set of points. Biometrika 52 1965 331--343. MR0207004
  • M. Meckes. Monotonicity of volumes of random simplices In: Recent Trends in Convex and Discrete Geometry. AMS Special Session 2006, San Antonio, Texas
  • Milman, V. D.; Pajor, A. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed $n$-dimensional space. Geometric aspects of functional analysis (1987–88), 64--104, Lecture Notes in Math., 1376, Springer, Berlin, 1989. MR1008717
  • Preparata, Franco P.; Shamos, Michael Ian. Computational geometry. An introduction. Texts and Monographs in Computer Science. Springer-Verlag, New York, 1985. xii+390 pp. ISBN: 0-387-96131-3 MR0805539
  • Rademacher, Luis. On the monotonicity of the expected volume of a random simplex. Mathematika 58 (2012), no. 1, 77--91. MR2891161
  • Reitzner, Matthias. The combinatorial structure of random polytopes. Adv. Math. 191 (2005), no. 1, 178--208. MR2102847
  • Reitzner, Matthias. Random polytopes. New perspectives in stochastic geometry, 45--76, Oxford Univ. Press, Oxford, 2010. MR2654675
  • Schneider, Rolf; Weil, Wolfgang. Stochastic and integral geometry. Probability and its Applications (New York). Springer-Verlag, Berlin, 2008. xii+693 pp. ISBN: 978-3-540-78858-4 MR2455326
  • Vu, V. H. Sharp concentration of random polytopes. Geom. Funct. Anal. 15 (2005), no. 6, 1284--1318. MR2221249

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.