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 metadatas

Cited literature [22 references]  Display  Hide  Download


https://hal.inria.fr/hal-01018174
Contributor : Ross Hemsley <>
Submitted on : Thursday, July 3, 2014 - 5:17:39 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on : Friday, October 3, 2014 - 11:57:14 AM

Files

aofa.pdf
Publisher files allowed on an open archive

Identifiers

  • 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. ⟨hal-01018174⟩

Share

Metrics

Record views

480

Files downloads

348