Efficiently navigating a random Delaunay triangulation

DOI10.1002/rsa.20630zbMath1331.68246arXiv1402.6148OpenAlexW1686685697MaRDI QIDQ2789543

Olivier Devillers, Nicolas Broutin, Ross Hemsley

Publication date: 1 March 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.6148

zbMATH Keywords

Delaunay triangulationroutingpoint locationstretch factorrandomised analysisPoisson Delaunay triangulation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (6)

Upper and Lower Bounds for Online Routing on Delaunay Triangulations ⋮ Walking in a Planar Poisson–Delaunay Triangulation: Shortcuts in the Voronoi Path ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Expected length of the Voronoi path in a high dimensional Poisson-Delaunay triangulation ⋮ The maximal degree in a Poisson-Delaunay graph

Cites Work

• Unnamed Item
• Memoryless routing in convex subdivisions: random walks are optimal
• On the stabbing number of a random Delaunay triangulation
• Guide to wireless mesh networks
• A note on point location in Delaunay triangulations of random points
• Expected time analysis for Delaunay point location
• Competitive online routing in geometric graphs
• Navigation on a Poisson point process
• WALKING IN A TRIANGULATION
• Asymptotics of geometrical navigation on a random set of points in the plane
• Online Routing in Triangulations
• Large deviations for sums of partly dependent random variables
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• Stochastic Geometry and Wireless Networks: Volume I Theory
• Improved upper bound on the stretch factor of delaunay triangulations
• Geometrically aware communication in random wireless networks
• Concentration of Measure for the Analysis of Randomized Algorithms

This page was built for publication: Efficiently navigating a random Delaunay triangulation