Skip to Main content Skip to Navigation
Journal articles

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
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Keywords : Random distribution Point location Routing Walking strategies
Document type :
Journal articles
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download

vignette.png
vignette.png
https://hal.inria.fr/hal-01477030
Contributor : Olivier Devillers <>
Submitted on : Sunday, February 26, 2017 - 7:32:49 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Long-term archiving on: : Saturday, May 27, 2017 - 12:33:05 PM

Files

Vignette du document
paper.pdf
Files produced by the author(s)

Identifiers

Collections

INRIA | UNIV-LORRAINE | LORIA | LORIA-ALGO | CNRS

Citation

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, Springer Verlag, 2018, 60 (1), pp.200--219. ⟨10.1007/s00454-017-9866-y⟩. ⟨hal-01477030⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

542

Files downloads

318

 

Contact                    Legal Notice                    Personal Data