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



https://hal.inria.fr/hal-00833774
Contributeur : Olivier Devillers <>
Soumis le : jeudi 13 juin 2013 - 14:57:59
Dernière modification le : vendredi 21 juillet 2017 - 10:49:40
Document(s) archivé(s) le : samedi 14 septembre 2013 - 04:14:03

Fichiers

hal-version.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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>

Partager

Métriques

Consultations de
la notice

579

Téléchargements du document

183