hal-00758686, version 1
The monotonicity of f-vectors of random polytopes
Olivier Devillers
1Marc Glisse
a, 1Xavier Goaoc
2Guillaume Moroz
2Matthias Reitzner 3
N° RR-8154 (2012)
Résumé : Let K be a compact convex body in Rd, let Kn be the convex hull of n points chosen uniformly and independently in K, and let fi(Kn) denote the number of i-dimensional faces of Kn. We show that for planar convex sets, E(f0(Kn)) is increasing in n. In dimension d>=3 we prove that if lim( E((f[d -1](Kn))/(An^c)->1 when n->infinity for some constants A and c > 0 then the function E(f[d-1](Kn)) 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.
- a – INRIA
- 1 : GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
- INRIA
- 2 : VEGAS (INRIA Nancy - Grand Est / LORIA)
- INRIA – CNRS : UMR7503 – Université de Lorraine
- 3 : Institut für Mathematik
- Universitat Osnabruck
- Domaine : Informatique/Géométrie algorithmique
- Mots-clés : Computational geometry – Stochastic geometry – Convex hull – Complexity
- Référence interne : RR-8154
- hal-00758686, version 1
- http://hal.inria.fr/hal-00758686
- oai:hal.inria.fr:hal-00758686
- Contributeur : Olivier Devillers
- Soumis le : Jeudi 29 Novembre 2012, 17:10:36
- Dernière modification le : Mardi 4 Décembre 2012, 10:42:07






Documents associés

Exporter