Published in

Computational Geometry Laboratory, Journal of Computational Geometry, (Vol 7), p. No 1 (2016)-

DOI: 10.20382/jocg.v7i1a16

Links

Tools

Export citation

Search in Google Scholar

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

Journal article published in 2016 by Olivier Devillers ORCID, Ross Hemsley
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Green circle
Published version: archiving allowed
Data provided by SHERPA/RoMEO

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, for any pair of vertices $(s,t)$ inside $[0,n]^2$, the ratio between the longest and shortest visibility walks between $s$ and $t$ is bounded by a constant 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.