Volume 3 (2020)
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.

Metadata

DOI10.5802/ahl.44
Keywords Random polytope, floating body, $\varepsilon $-nets.

Abstract

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.


References

[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