Random polytopes and the wet part for arbitrary probability distributions

Bárány, Imre; Fradelizi, Matthieu; Goaoc, Xavier; Hubard, Alfredo; Rote, Günter

Annales Henri Lebesgue, Tome 3 (2020), pp. 701-715.

Nous examinons comment la mesure et le nombre de sommets de l’enveloppe convexe d’un échantillon aléatoire de $n$ points tirés selon une mesure de probabilité arbitraire sur ${ℝ}^d$ sont reliés à la partie immergée de la mesure. Cela étend des résultats classiques pour la mesure uniforme sur un convexe établis par Bárány et Larman en 1988. La minoration de Bárány et Larman est toujours vraie dans ce cadre général mais la majoration doit être affaiblie d’un facteur $logn$. Nous montrons par un exemple que cette borne est optimale.

We examine how the measure and the number of vertices of the convex hull of a random sample of $n$ points from an arbitrary probability measure in ${ℝ}^d$ relate to the wet part of that measure. This extends classical results for the uniform distribution from a convex set proved by Bárány and Larman in 1988. The lower bound of Bárány and Larman continues to hold in the general setting, but the upper bound must be relaxed by a factor of $logn$. We show by an example that this is tight.

Classification : 52B05, 52A22
Mots-clés : Random polytope, floating body, $\epsilon$-nets.

[BD97] Bárány, Imre; Dalla, Leoni Few points to generate a random polytope, Mathematika, Volume 44 (1997) no. 2, pp. 325-331 | DOI | MR | Zbl

[Bee15] Beermann, Mareen Random polytopes, Ph. D. Thesis, University of Osnabrück (Germany) (2015) (https://repositorium.ub.uni-osnabrueck.de/bitstream/urn:nbn:de:gbv:700-2015062313276/1/thesis_beermann.pdf)

[BL88] Bárány, Imre; Larman, David G. Convex bodies, economic cap coverings, random polytopes, Mathematika, Volume 35 (1988) no. 2, pp. 274-291 | DOI | MR | Zbl

[BR17] Beermann, Mareen; Reitzner, Matthias Monotonicity of functionals of random polytopes (2017) (https://arxiv.org/abs/1706.08342)

[Bár89] Bárány, Imre Intrinsic volumes and $f$-vectors of random polytopes, Math. Ann., Volume 285 (1989) no. 4, pp. 671-699 | DOI | MR | Zbl

[DGG + 13] Devillers, Olivier; Glisse, Marc; Goaoc, Xavier; Moroz, Guillaume; Reitzner, Matthias The monotonicity of $f$-vectors of random polytopes, Electron. Commun. Probab., Volume 18 (2013), 23, pp. 1-8 | MR | Zbl

[Efr65] Efron, Bradley The convex hull of a random set of points, Biometrika, Volume 52 (1965), pp. 331-343 | DOI | MR

[Har67] Harding, E. F. The number of partitions of a set of $N$ points in $k$ dimensions induced by hyperplanes, Proc. Edinb. Math. Soc., Volume 15 (1967) no. 4, pp. 285-289 | DOI | MR | Zbl

[HW87] Haussler, David; Welzl, Emo $\epsilon$-Nets and simplex range queries, Discrete Comput. Geom., Volume 2 (1987), pp. 127-151 | DOI | MR | Zbl

[KPW92] Komlós, János; Pach, János; Woeginger, Gerhard Almost tight bounds for $\epsilon$-nets, Discrete Comput. Geom., Volume 7 (1992) no. 2, pp. 163-173 | DOI | MR | Zbl

[KTZ19] Kabluchko, Zakhlar; Thäle, Christoph; Zaporozhets, Dmitry Beta polytopes and Poisson polyhedra: $f$-vectors and angles (2019) (https://arxiv.org/abs/1805.01338)

[Mat02] Matoušek, Jiří Lectures on Discrete Geometry, Graduate Texts in Mathematics, 212, Springer, 2002 | MR | Zbl

[PA95] Pach, János; Agarwal, Pankaj K. Combinatorial Geometry, John Wiley & Sons, 1995 | Zbl

[VC71] Vapnik, Vladimir N.; Chervonenkis, Alekseĭ Ya. On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., Volume 16 (1971), pp. 264-280 | DOI | Zbl

[Vu05] Vu, Van H. Sharp concentration of random polytopes, Geom. Funct. Anal., Volume 15 (2005) no. 6, pp. 1284-1318 | MR | Zbl