Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Computational Geometry and Applications Année : 2018

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

Résumé

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$.
Fichier principal
Vignette du fichier
paper.pdf (844.11 Ko) Télécharger le fichier
Vignette du fichier
vignette.png (15.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...

Dates et versions

hal-01712628 , version 1 (19-02-2018)

Identifiants

Citer

Olivier Devillers, Louis Noizet. Walking in a Planar Poisson-Delaunay Triangulation: Shortcuts in the Voronoi Path. International Journal of Computational Geometry and Applications, 2018, 28 (3), pp.255-269. ⟨10.1142/S0218195918500061⟩. ⟨hal-01712628⟩
284 Consultations
214 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More