Skip to Main content Skip to Navigation
Reports

The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$

Olivier Devillers 1 Ross Hemsley 2
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We show that the memoryless routing algorithms Greedy Walk, Compass Walk, and all variants of visibility walk based on orientation predicates are asymptotically optimal in the average case on the Delaunay triangulation. More specifically, we consider the Delaunay triangulation of an unbounded Poisson point process of unit rate and demonstrate that the worst-case path between any two vertices inside a domain of area $n$ has a number of steps that is not asymptotically more than the shortest path which exists between those two vertices with probability converging to one (as long as the vertices are sufficiently far apart.) As a corollary, it follows that the worst-case path has $O(\sqrt{n}\,)$ steps in the limiting case, under the same conditions. Our results have applications in routing in mobile networks and also settle a long-standing conjecture in point location using walking algorithms. Our proofs use techniques from percolation theory and stochastic geometry.
Document type :
Reports
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download


https://hal.inria.fr/hal-01216212
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, October 15, 2015 - 5:12:56 PM
Last modification on : Sunday, October 17, 2021 - 3:39:56 AM
Long-term archiving on: : Thursday, April 27, 2017 - 4:32:16 AM

Files

RR-8792.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01216212, version 1

Citation

Olivier Devillers, Ross Hemsley. The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$. [Research Report] RR-8792, INRIA. 2015, pp.25. ⟨hal-01216212⟩

Share

Metrics

Record views

526

Files downloads

262