A chaotic random convex hull

Olivier Devillers (1) , Marc Glisse (1) , Rémy Thomasse (1)

1 GEOMETRICA - Geometric computing

The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body in Rd is polynomial for a smooth body and polylogarithmic for a polytope. We construct a body whose expected size of the convex hull oscillates between these two behaviors when the number of points increases.

Domaines: Géométrie algorithmique [cs.CG]

Olivier Devillers, Marc Glisse, Rémy Thomasse. A chaotic random convex hull. AofA 2014- 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. ⟨hal-01015598⟩