Annales Henri Lebesgue

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

KeywordsRandom polytope, floating body,

ε

-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 $log n$ . 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 | Article | MR 1600549 | Zbl 0902.52002

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

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

[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 | Article | MR 1027765 | Zbl 0696.52005

[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 3044471 | Zbl 1359.60024

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

[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 | Article | MR 229128 | Zbl 0153.32802

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

[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 | Article | MR 1139078 | Zbl 0765.68209

[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, Volume 212, Springer, 2002 | MR 1899299 | Zbl 0999.52006

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

[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 | Article | Zbl 0247.60005

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