8481 articles  [version française]

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 () a, 1, Xavier Goaoc () 2, Guillaume Moroz () 2, Matthias Reitzner 3

N° RR-8154 (2012)

Abstract: 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
  • Domain : Computer Science/Computational Geometry
  • Keywords : Computational geometry – Stochastic geometry – Convex hull – Complexity
  • Internal note : RR-8154
 
  • hal-00758686, version 1
  • http://hal.inria.fr/hal-00758686
  • oai:hal.inria.fr:hal-00758686
  • From: Olivier Devillers <>
  • Submitted on: Thursday, 29 November 2012 17:10:36
  • Updated on: Tuesday, 4 December 2012 10:42:07