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
Résumé : L'analyse en moyenne de structure de données et d'algorithmes géométriques est fréquemment utilisée en géométrie algorithmique, un domaine ou' l'analyse dans le cas le pire est souvent très pessimiste. La difficulté de ce type d'analyse fait que les modèles probabilistes utilisés restent simples et relativement éloignées de données réalistes. Nous présentons une nouvelle approche pour l'analyse des structures géométriques. Nos résultats sont seulement 'a des facteurs logarithmiques près, mais notre méthode est plus simple que les classiques du domaine et nous réussissons 'a analyser de nouveau type de distribution liée à la smooth analysis. Nous illustrons notre méthode sur deux structures classiques: l'enveloppe convexe et la triangulation de Delaunay. Plus précisément, nous démontrons simplement le fait, classique, que n points uniformément distribués dans une boule de Rd ont une enveloppe convexe et une triangulation de Delaunay dont l'espérance de la taille est respectivement Θ~(n^((d+1)/(d-1)) ) et Θ~(n). Nous démontrons ensuite que si on se donne ensemble de n points bien distribu ́es sur une sphère, par exemple un (ε, κ)-échantillon de la sphère, et qu'on le perturbe ensuite en déplaçant chaque point uniformément d'une distance δ à partir de sa position initiale, alors l'espérance de la taille de l'enveloppe convexe de ces points est Θ~( sqrt(n)^(1−1/d) δ^(-(d-1/d)/4)). .
Type de document :
Rapport
[Research Report] RR-8168, INRIA. 2012
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00761171
Contributeur : Olivier Devillers <>
Soumis le : mercredi 5 décembre 2012 - 09:39:10
Dernière modification le : vendredi 21 juillet 2017 - 10:58:24
Document(s) archivé(s) le : samedi 17 décembre 2016 - 20:29:50

Fichier

RR-8168.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00761171, version 1

Citation

Olivier Devillers, Marc Glisse, Xavier Goaoc. Complexity analysis of random geometric structures made simpler. [Research Report] RR-8168, INRIA. 2012. 〈hal-00761171〉

Partager

Métriques

Consultations de
la notice

377

Téléchargements du document

271