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

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, for any pair of vertices (s, t) inside a square of area n, 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.
Type de document :
Article dans une revue
Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (1), pp.332-359. 〈http://jocg.org/v7n1p16〉. 〈10.20382/jocg.v7i1a16〉

Littérature citée [20 références]

https://hal.inria.fr/hal-01348831
Contributeur : <>
Soumis le : lundi 25 juillet 2016 - 18:06:01
Dernière modification le : samedi 18 février 2017 - 01:14:42
Document(s) archivé(s) le : mercredi 26 octobre 2016 - 15:04:40

Fichiers

jocg.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Olivier Devillers, Ross Hemsley. The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$ . Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2016, 7 (1), pp.332-359. 〈http://jocg.org/v7n1p16〉. 〈10.20382/jocg.v7i1a16〉. 〈hal-01348831〉

Métriques

Consultations de la notice

231

Téléchargements de fichiers