Complexity Analysis of Random Geometric Structures Made Simpler

Olivier Devillers 1 Marc Glisse 1 Xavier Goaoc 2
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, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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) ).
Type de document :
Communication dans un congrès
29th Annual Symposium on Computational Geometry, Jun 2013, Rio, Brazil. pp.167-175, 2013, <10.1145/2462356.2462362>
Liste complète des métadonnées
Contributeur : Olivier Devillers <>
Soumis le : jeudi 13 juin 2013 - 14:57:59
Dernière modification le : jeudi 9 février 2017 - 15:47:14
Document(s) archivé(s) le : samedi 14 septembre 2013 - 04:14:03


Fichiers produits par l'(les) auteur(s)




Olivier Devillers, Marc Glisse, Xavier Goaoc. Complexity Analysis of Random Geometric Structures Made Simpler. 29th Annual Symposium on Computational Geometry, Jun 2013, Rio, Brazil. pp.167-175, 2013, <10.1145/2462356.2462362>. <hal-00833774>



Consultations de
la notice


Téléchargements du document