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, ACIG - Algorithms, Computation, Image and Geometry
3 Institut für Mathematik
FB6/Institut für Mathematik - Institut für Mathematik [Osnabrück]
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.
Document type :
Reports
[Research Report] RR-8154, INRIA. 2012, pp.10


https://hal.inria.fr/hal-00758686
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 29, 2012 - 5:10:36 PM
Last modification on : Wednesday, July 29, 2015 - 1:23:14 AM

Files

RR-8154.pdf
fileSource_public_author

Identifiers

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

Collections

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>

Export

Share

Metrics

Consultation de
la notice

161

Téléchargement du document

103