The monotonicity of f-vectors of random polytopes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

The monotonicity of f-vectors of random polytopes

Olivier Devillers
Marc Glisse

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.
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.
Fichier principal
Vignette du fichier
RR-8154.pdf (466.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00758686 , version 1 (29-11-2012)

Identifiants

Citer

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⟩
263 Consultations
188 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More