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

Chemins dans la triangulation planaire de Poisson-Delaunay:\\ Raccourcis dans la marche de Voronoi

Olivier Devillers (1) , Louis Noizet (2, 1)

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
2 ENS-PSL - École normale supérieure - Paris

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 $O(1/\sqrt{n})$. We investigate the length of possible shortcuts in this path, and defined 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 path in Delaunay triangulation such as the upper path whose expected length is $35/3\pi^2\simeq 1.18$.

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$.

Domaines: Géométrie algorithmique [cs.CG]

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⟩