HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

Contributor : Ross Hemsley Connect in order to contact the contributor
Submitted on : Thursday, July 3, 2014 - 5:17:39 PM
Last modification on : Friday, January 21, 2022 - 3:18:04 AM
Long-term archiving on: : Friday, October 3, 2014 - 11:57:14 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01018174, version 1



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⟩



Record views


Files downloads