Random polytopes and the wet part for arbitrary probability distributions

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

doi:10.5802/ahl.44

Bárány, Imre ¹; Fradelizi, Matthieu ²; Goaoc, Xavier ³; Hubard, Alfredo ⁴; Rote, Günter ⁵

¹ Rényi Institute of Mathematics Hungarian Academy of Sciences PO Box 127, 1364 Budapest and Department of Mathematics University College London Gower Street, London WC1E 6BT (UK)
² Université Paris-Est, LAMA (UMR 8050) UPEM, UPEC, CNRS 77454 Marne-la-Vallée (France)
³ Université de Lorraine CNRS,Inria, LORIA 54000 Nancy (France)
⁴ Université Paris-Est, Marne-la-Vallée Laboratoire d’Informatique Gaspard Monge 5 Boulevard Descartes 77420 Champs-sur-Marne (France)
⁵ Freie Universität Berlin Institut für Informatik Takustraße 9 14195 Berlin (Germany)

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

Abstract
Résumé

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 $log n$ . We show by an example that this is tight.

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 $log n$ . Nous montrons par un exemple que cette borne est optimale.

Received: 2019-02-23
Accepted: 2019-11-08
Published online: 2020-08-24

DOI: 10.5802/ahl.44

Classification: 52B05, 52A22
Keywords: Random polytope, floating body, $\varepsilon $-nets.

Author's affiliations:

Bárány, Imre ¹; Fradelizi, Matthieu ²; Goaoc, Xavier ³; Hubard, Alfredo ⁴; Rote, Günter ⁵

@article{AHL_2020__3__701_0,
     author = {B\'ar\'any, Imre and Fradelizi, Matthieu and Goaoc, Xavier and Hubard, Alfredo and Rote, G\"unter},
     title = {Random polytopes and the wet part for arbitrary probability distributions},
     journal = {Annales Henri Lebesgue},
     pages = {701--715},
     publisher = {\'ENS Rennes},
     volume = {3},
     year = {2020},
     doi = {10.5802/ahl.44},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/ahl.44/}
}

TY  - JOUR
AU  - Bárány, Imre
AU  - Fradelizi, Matthieu
AU  - Goaoc, Xavier
AU  - Hubard, Alfredo
AU  - Rote, Günter
TI  - Random polytopes and the wet part for arbitrary probability distributions
JO  - Annales Henri Lebesgue
PY  - 2020
SP  - 701
EP  - 715
VL  - 3
PB  - ÉNS Rennes
UR  - http://archive.numdam.org/articles/10.5802/ahl.44/
DO  - 10.5802/ahl.44
LA  - en
ID  - AHL_2020__3__701_0
ER  -

%0 Journal Article
%A Bárány, Imre
%A Fradelizi, Matthieu
%A Goaoc, Xavier
%A Hubard, Alfredo
%A Rote, Günter
%T Random polytopes and the wet part for arbitrary probability distributions
%J Annales Henri Lebesgue
%D 2020
%P 701-715
%V 3
%I ÉNS Rennes
%U http://archive.numdam.org/articles/10.5802/ahl.44/
%R 10.5802/ahl.44
%G en
%F AHL_2020__3__701_0

Bárány, Imre; Fradelizi, Matthieu; Goaoc, Xavier; Hubard, Alfredo; Rote, Günter. Random polytopes and the wet part for arbitrary probability distributions. Annales Henri Lebesgue, Volume 3 (2020), pp. 701-715. doi : 10.5802/ahl.44. http://archive.numdam.org/articles/10.5802/ahl.44/

References
Cited by

[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 $ε$ -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 $ε$ -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

Cited by Sources: