s'authentifier
version française rss feed

hal-00758686, version 1

The monotonicity of f-vectors of random polytopes

Olivier Devillers (, http://www-sop.inria.fr/members/Olivier.Devillers/) 1, Marc Glisse () a1, Xavier Goaoc () 2, Guillaume Moroz () 2, Matthias 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.

  • 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
  • oai:hal.inria.fr:hal-00758686
  • Contributeur : 
  • Soumis le : Jeudi 29 Novembre 2012, 17:10:36
  • Dernière modification le : Mardi 4 Décembre 2012, 10:42:07
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...