Skip to Main content Skip to Navigation
Conference papers

Complexity Analysis of Random Geometric Structures Made Simpler

Mikhail Bogdanov 1 Olivier Devillers 1 Monique Teillaud 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Average-case analysis of data-structures or algorithms is com- monly used in computational geometry when the, more clas- sical, worst-case analysis is deemed overly pessimistic. Since these analyses are often intricate, the models of random geo- metric data that can be handled are often simplistic and far from "realistic inputs". We present a new simple scheme for the analysis of geometric structures. While this scheme only produces results up to a polylog factor, it is much simpler to apply than the classical techniques and therefore succeeds in analyzing new input distributions related to smoothed com- plexity analysis. We illustrate our method on two classical structures: con- vex hulls and Delaunay triangulations. Specifically, we give short and elementary proofs of the classical results that n points uniformly distributed in a ball in R^d have a convex hull and a Delaunay triangulation of respective expected d−1 complexities Θ(n^(d+1) ) and Θ(n). We then prove that if we start with n points well-spread on a sphere, e.g. an (epsilon,kappa)-sample of that sphere, and perturb that sample by moving each point randomly and uniformly within distance at most δ of its initial position, then the expected complexity of the convex hull of the resulting point set is Θ( n^(1/2-1/2d) δ^(-d/4+1/4d) ).
Document type :
Conference papers
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Thursday, June 13, 2013 - 2:39:54 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Document(s) archivé(s) le : Saturday, September 14, 2013 - 4:13:57 AM


Files produced by the author(s)




Mikhail Bogdanov, Olivier Devillers, Monique Teillaud. Complexity Analysis of Random Geometric Structures Made Simpler. Proceedings of the 29th Annual Symposium on Computational Geometry, Jun 2013, Rio, Brazil. pp.167-175, ⟨10.1145/2462356.2462362⟩. ⟨hal-00833760⟩



Record views


Files downloads