Premium
Efficiently navigating a random Delaunay triangulation
Author(s) -
Broutin Nicolas,
Devillers Olivier,
Hemsley Ross
Publication year - 2016
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20630
Subject(s) - delaunay triangulation , mathematics , binary logarithm , vertex (graph theory) , combinatorics , random walk , triangulation , regular polygon , point location , point (geometry) , constrained delaunay triangulation , domain (mathematical analysis) , mathematical proof , pitteway triangulation , point set triangulation , discrete mathematics , graph , statistics , geometry , mathematical analysis
Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. However, whilst a number of algorithms and existence proofs have been proposed, very little analysis is available for the properties of the paths generated and the computational resources required to generate them under a random distribution hypothesis for the input. In this paper we analyse a new deterministic planar navigation algorithm with constant spanning ratio (w.r.t the Euclidean distance) which follows vertex adjacencies in the Delaunay triangulation. We call this strategy cone walk . We prove that given n uniform points in a smooth convex domain of unit area, and for any start point z and query point q ; cone walk applied to z and q will access at most O ( | z q | n + log 7 n ) sites with complexity O ( | z q | n log log n + log 7 n ) with probability tending to 1 as n goes to infinity. We additionally show that in this model, cone walk is ( log 3 + ξ n ) ‐memoryless with high probability for any pair of start and query point in the domain, for any positive ξ . We take special care throughout to ensure our bounds are valid even when the query points are arbitrarily close to the border. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 95–136, 2016