The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$ - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Computational Geometry Année : 2016

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

Ross Hemsley
  • Fonction : Auteur
  • PersonId : 772922
  • IdRef : 184707196

Résumé

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.
Fichier principal
Vignette du fichier
jocg.pdf (1.04 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (15.67 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01348831 , version 1 (25-07-2016)

Identifiants

Citer

Olivier Devillers, Ross Hemsley. The worst visibility walk in a random Delaunay triangulation is $O(\sqrt{n})$ . Journal of Computational Geometry, 2016, 7 (1), pp.332-359. ⟨10.20382/jocg.v7i1a16⟩. ⟨hal-01348831⟩
343 Consultations
154 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More