A cone can help you find your way in a Poisson Delaunay triangulation - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2012

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

(1) , (2) , (2)
1
2
Nicolas Broutin
  • Function : Author
  • PersonId : 874919
Olivier Devillers
Ross Hemsley
  • Function : Author
  • PersonId : 934731

Abstract

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
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

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

Identifiers

  • HAL Id : hal-00769529 , version 2

Cite

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⟩
325 View
364 Download

Share

Gmail Facebook Twitter LinkedIn More