The monotonicity of f-vectors of random polytopes

Olivier Devillers 1 Marc Glisse 1 Xavier Goaoc 2 Guillaume Moroz 2 Matthias Reitzner 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 Institut für Mathematik
FB6/Institut für Mathematik - Institut für Mathematik [Osnabrück]
Résumé : Soit K un domaine convexe et compact de Rd, Kn l'enveloppe convexe de n points choisis uniformément et indépendamment dans K, et fi(Kn) le nombre de faces de Kn de dimension i. Nous montrons que pour des convexes du plan, E(f0(Kn)) est croissant avec n. En dimension d >= 3 nous montrons que si lim( E((f[d -1](Kn))/(An^c)->1 quand n->infini pour des constantes A et c a> 0 alors la fonction nE(f[d-1](Kn)) est croissante pour n suffisamment grand. En particulier, le nombre de facettes de l'enveloppe convexe de n points aléatoires distribués uniformément et indépendamment dans un convexe compact à bord lisse est asymptotiquement croissant. Notre démonstration utilise un argument d'échantillonnage aléatoire.
Type de document :
Rapport
[Research Report] RR-8154, INRIA. 2012, pp.10


https://hal.inria.fr/hal-00758686
Contributeur : Olivier Devillers <>
Soumis le : jeudi 29 novembre 2012 - 17:10:36
Dernière modification le : jeudi 22 septembre 2016 - 14:31:21

Fichiers

RR-8154.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00758686, version 1
  • ARXIV : 1211.7020

Citation

Olivier Devillers, Marc Glisse, Xavier Goaoc, Guillaume Moroz, Matthias Reitzner. The monotonicity of f-vectors of random polytopes. [Research Report] RR-8154, INRIA. 2012, pp.10. <hal-00758686>

Exporter

Partager

Métriques

Consultations de
la notice

259

Téléchargements du document

154