Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path

Olivier Devillers 1 Louis Noizet 2, 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Résumé : Soit $X_n$ un processus ponctuel de Poisson planaire d'intensité $n$. Nous donnons une nouvelle démonstration que l'espérance de la longueur du chemin de Voronoï entre $(0,0)$ et $(1,0)$ dans la triangulation de Delaunay associée à $X_n$ est $\tfrac{4}{\pi}\simeq 1.27$ quand $n$ tends vers l'infini; nous démontrons aussi que la variance de cette longueur est $O(1/\sqrt{n})$. Nous étudions la longueurs gagnées par certains raccourcis dans le chemin de Voronoi et arrivons à exprimer cette longueur comme une intégrale dont l'évaluation numérique est $\simeq 1.16$. Le chemin de Voronoi raccourci a la propriété d'être {\em défini localement}; et il est plus court que les autres chemins défini localement déjà étudié tel que le {\em chemin supérieur} dont la longueur moyenne est $35/3\pi^2\simeq 1.18$.
Type de document :
Rapport
[Research Report] RR-8946, INRIA Nancy. 2016
Liste complète des métadonnées



https://hal.inria.fr/hal-01353585
Contributeur : Olivier Devillers <>
Soumis le : mardi 16 août 2016 - 17:34:36
Dernière modification le : mercredi 28 septembre 2016 - 16:19:48
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:46:27

Identifiants

  • HAL Id : hal-01353585, version 1

Citation

Olivier Devillers, Louis Noizet. Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path. [Research Report] RR-8946, INRIA Nancy. 2016. <hal-01353585>

Partager

Métriques

Consultations de
la notice

181

Téléchargements du document

186