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
Résumé : Nous montrons que les algorithmes de routage sans mémoire de marche gloutonne, de marche au compas et toutes les variantes de marche par visibilité sont asymptotiquement optimale en moyenne pour la triangulation de Delaunay. Plus précisément, nous considérons la triangulation de Delaunay d'un processus de Poisson non borné d'intensité un et démontrons que le rapport entre les nombre d'étapes du 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 et réponds à une conjecture sur les algorithmes de localisation par marche dans les triangulations. Nos démonstrations utilisent des résultats de percolation et de géométrie stochastique.
Type de document :
Rapport
[Research Report] RR-8792, INRIA. 2015, pp.25
Liste complète des métadonnées



https://hal.inria.fr/hal-01216212
Contributeur : Olivier Devillers <>
Soumis le : jeudi 15 octobre 2015 - 17:12:56
Dernière modification le : samedi 18 février 2017 - 01:14:46
Document(s) archivé(s) le : jeudi 27 avril 2017 - 04:32:16

Fichiers

RR-8792.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

256

Téléchargements du document

110