A cone can help you find your way in a Poisson Delaunay triangulation

Nicolas Broutin 1 Olivier Devillers 2 Ross Hemsley 2
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Résumé : Les stratégies de localisation par marche dans une triangulation de taille n sont un outil standard de localisation, et sont en général annoncées de complexité moyenne Θ(√n ). Cette conjecture n'a étée montrée formellement que par Devroye, Lemaire, et Moreau [Comp Geom-Theor Appl, vol. 29, 2004], dans le cas particulier de la marche rectiligne dans laquelle le fait pour un triangle donné de participer à la marche peut être décidé sans connaître les autres points. Dans cet article, nous analysons une marche différente qui va de sommet en sommet en suivant des arètes de la triangulation pour se rapprocher de la requète. Nous appellons cette marche la marche conique. Nous montrons que la marche conique visite Θ(√n ) sommets et peut être déterminée en temps Θ(√n ). Nous donnons des bornes explicites sur les constantes.
Type de document :
Rapport
[Research Report] RR-8194, INRIA. 2012
Liste complète des métadonnées

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


https://hal.inria.fr/hal-00769529
Contributeur : Olivier Devillers <>
Soumis le : jeudi 3 avril 2014 - 14:51:38
Dernière modification le : mardi 17 avril 2018 - 11:28:11
Document(s) archivé(s) le : lundi 10 avril 2017 - 09:41:03

Fichiers

RR_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00769529, version 2

Collections

Citation

Nicolas Broutin, Olivier Devillers, Ross Hemsley. A cone can help you find your way in a Poisson Delaunay triangulation. [Research Report] RR-8194, INRIA. 2012. 〈hal-00769529v2〉

Partager

Métriques

Consultations de la notice

494

Téléchargements de fichiers

317