Efficiently navigating a random Delaunay triangulation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Random Structures and Algorithms Année : 2016

Efficiently navigating a random Delaunay triangulation

Résumé

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant competitiveness which follows vertex adjacencies in the Delaunay triangulation. We call this strategy \emph{cone walk}. We prove that given n uniform points in a smooth convex domain of unit area, and for any start point z and query point q; cone walk applied to z and q will access at most O(|zq| √n + log^7 n) sites with complexity O(|zq| √n log log n + log^7 n) with probability tending to 1 as n goes to infinity. We additionally show that in this model, cone walk is (log^(3+x) n)-memoryless with high probability for any pair of start and query point in the domain, for any positive x. We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border.
Fichier principal
Vignette du fichier
RSA.pdf (1.66 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (72.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00940743 , version 1 (02-02-2014)
hal-00940743 , version 2 (03-04-2014)
hal-00940743 , version 3 (11-04-2016)

Identifiants

Citer

Nicolas Broutin, Olivier Devillers, Ross Hemsley. Efficiently navigating a random Delaunay triangulation. Random Structures and Algorithms, 2016, 49 (1), pp.95--136. ⟨10.1002/rsa.20630⟩. ⟨hal-00940743v3⟩
1101 Consultations
630 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More