Efficiently Navigating a Random Delaunay Triangulation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Efficiently Navigating a Random Delaunay Triangulation

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

Résumé

Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. Whilst many algorithms have been proposed, very little theoretical analysis is available for the properties of the paths generated or the computational resources required to generate them. In this work, we propose and analyse a new planar navigation algorithm for the Delaunay triangulation. We then demonstrate a number of strong theoretical guarantees for the algorithm when it is applied to a random set of points in a convex region.
Fichier principal
Vignette du fichier
aofa.pdf (197.1 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (72.62 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Format : Figure, Image
Loading...

Dates et versions

hal-01018174 , version 1 (03-07-2014)

Identifiants

  • HAL Id : hal-01018174 , version 1

Citer

Nicolas Broutin, Olivier Devillers, Ross Hemsley. Efficiently Navigating a Random Delaunay Triangulation. AofA 2014 - 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. ⟨hal-01018174⟩

Collections

INRIA INRIA2 ANR
235 Consultations
215 Téléchargements

Partager

Gmail Facebook X LinkedIn More