Expected Length of the Voronoi Path in a High Dimensional Poisson-Delaunay Triangulation

Pedro Machado Manhães de Castro (1) , Olivier Devillers (2)

1 UFPE - Universidade Federal de Pernambuco [Recife]
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm

Let X be a d dimensional Poisson point process. We prove that the expected length of the Voronoi path between two points at distance 1 in the Delaunay triangulation associated with X is sqrt(2d/π) + O(d^(−1/2) when d → ∞. In any dimension, we also provide a precise interval containing the actual value; in 3D the expected length is between 1.4977 and 1.50007.

Mots clés: Point location; Random distribution; Walking strategies; Routing

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

Pedro Machado Manhães de Castro, Olivier Devillers. Expected Length of the Voronoi Path in a High Dimensional Poisson-Delaunay Triangulation. Discrete and Computational Geometry, 2018, 60 (1), pp.200--219. ⟨10.1007/s00454-017-9866-y⟩. ⟨hal-01477030⟩