Efficiently Navigating a Random 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
Abstract : 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.
Type de document :
Communication dans un congrès
AofA 2014 - 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Jun 2014, Paris, France. 2014, 〈https://hal.inria.fr/hal-01077251〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01018174
Contributeur : Ross Hemsley <>
Soumis le : jeudi 3 juillet 2014 - 17:17:39
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : vendredi 3 octobre 2014 - 11:57:14

Fichiers

aofa.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01018174, version 1

Collections

Citation

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. 2014, 〈https://hal.inria.fr/hal-01077251〉. 〈hal-01018174〉

Partager

Métriques

Consultations de la notice

436

Téléchargements de fichiers

269