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

1 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Let $X_n$ be a planar Poisson point process of intensity $n$. We give a new proof that the expected length of the Voronoi path between $(0,0)$ and $(1,0)$ in the Delaunay triangulation associated with $X_n$ is $\tfrac{4}{\pi}\simeq 1.27$ when $n$ goes to infinity; and we also prove that the variance of this length is $\Theta(1/\sqrt{n})$. We investigate the length of possible shortcuts in this path, and define a shortened Voronoi path whose expected length can be expressed as an integral that is numerically evaluated to $\simeq 1.16$. The shortened Voronoi path has the property to be {\em locally defined}; and is shorter than the previously known locally defined paths in Delaunay triangulation such as the upper path whose expected length is $35/3\pi^2\simeq 1.18$.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2018, 28 (3), pp.255-269. 〈https://www.worldscientific.com/doi/10.1142/S0218195918500061〉. 〈10.1142/S0218195918500061〉

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

https://hal.inria.fr/hal-01712628
Contributeur : Olivier Devillers <>
Soumis le : lundi 19 février 2018 - 16:32:14
Dernière modification le : jeudi 7 février 2019 - 16:23:50
Document(s) archivé(s) le : samedi 5 mai 2018 - 20:47:43

### Fichiers

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

### Citation

Olivier Devillers, Louis Noizet. Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2018, 28 (3), pp.255-269. 〈https://www.worldscientific.com/doi/10.1142/S0218195918500061〉. 〈10.1142/S0218195918500061〉. 〈hal-01712628〉

### Métriques

Consultations de la notice

## 265

Téléchargements de fichiers