HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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
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 $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$.
Document type :
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Tuesday, August 16, 2016 - 5:34:36 PM
Last modification on : Thursday, March 17, 2022 - 10:08:37 AM
Long-term archiving on: : Thursday, November 17, 2016 - 10:46:27 AM



  • HAL Id : hal-01353585, version 1


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⟩



Record views


Files downloads