Efficiently Navigating a Random Delaunay Triangulation

Nicolas Broutin 1 Olivier Devillers 2 Ross Hemsley 2
1 RAP - Networks, Algorithms and Probabilities
Inria Paris-Rocquencourt
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.
Keywords : Delaunay Triangulation Routing Point Location Randomised Analysis
Document type :
Conference papers
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

vignette.png
vignette.png
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

INRIA | INRIA-ROCQ

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

480

Files downloads

348

Contact

CCSD