A cone can help you find your way in a Poisson Delaunay triangulation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

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

Nicolas Broutin
  • Fonction : Auteur
  • PersonId : 874919
Olivier Devillers
Ross Hemsley
  • Fonction : Auteur
  • PersonId : 934731

Résumé

Walking strategies are a standard tool for point location in a triangulation of size n. Although often claimed to be Θ(√n ) under random distribution hypotheses, this conjecture has only been formally proved by Devroye, Lemaire, and Moreau [Comp Geom-Theor Appl, vol. 29, 2004], in the case of the so called straight walk which has the very specific property that deciding whether a given (Delaunay) triangle belongs to the walk may be determined without looking at the other sites. In this paper we analyze a different walking strategy that follows vertex neighbour relations to move towards the query. We call this walk cone vertex walk. We prove that cone vertex walk visits Θ(√n ) vertices and can be constructed in Θ(√n ) time. We provide explicit bounds on the hidden constants.
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.
Fichier principal
Vignette du fichier
RR_new.pdf (550.65 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (64.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

hal-00769529 , version 1 (02-01-2013)
hal-00769529 , version 2 (03-04-2014)

Identifiants

  • HAL Id : hal-00769529 , version 2

Citer

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⟩
339 Consultations
403 Téléchargements

Partager

Gmail Facebook X LinkedIn More