Links

Tools

Export citation

Search in Google Scholar

The worst visibility walk in a random Delaunay triangulation is O( √ n) ; La pire marche par visibilité dans une triangulation de Delaunay de points aléatoires est en $O(\sqrt{n})$

Report published in 2015 by Olivier Devillers ORCID, Ross Hemsley
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Question mark in circle
Preprint: policy unknown
Question mark in circle
Postprint: policy unknown
Question mark in circle
Published version: policy unknown

Abstract

We show that the memoryless routing algorithms Greedy Walk, Compass Walk,and all variants of visibility walk based on orientation predicates are asymptotically optimalin the average case on the Delaunay triangulation. Morespecifically, we consider the Delaunay triangulation of an unbounded Poisson pointprocess of unit rate and demonstrate that the worst-case path between any twovertices inside a domain of area $n$ has a number of steps that is not asymptotically morethan the shortest path which exists between those two vertices with probabilityconverging to one (as long as the vertices are sufficiently far apart.) As acorollary, it follows that the worst-case path has $O(\sqrt{n}\,)$ steps in thelimiting case, under the same conditions. Our results have applications inrouting in mobile networks and also settle a long-standing conjecture in pointlocation using walking algorithms. Our proofs use techniques frompercolation theory and stochastic geometry. ; Nous montrons que les algorithmes de routage sans mémoire de marchegloutonne, de marche au compas et toutes les variantes de marche parvisibilité sont asymptotiquement optimale en moyenne pour latriangulation de Delaunay.Plus précisément, nous considérons la triangulation de Delaunay d'unprocessus de Poisson non borné d'intensité un et démontrons que lerapport entre les nombre d'étapesdu pire et du meilleur chemin entre deux sommets suffisamment loin dans un domaine d'aire $n$est borné par une constante avec une probabilité convergeant vers 1.On en déduit comme corollaire que le pire chemin a au plus$O(\sqrt{n}\,)$ étapes.Ce résultat a des applications au routage dans les réseaux mobiles etréponds à une conjecture sur les algorithmes de localisation parmarche dans les triangulations.Nos démonstrations utilisent des résultats de percolation et degéométrie stochastique.