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

Pedro Machado Manhães de Castro; Olivier Devillers

doi:10.1007/s00454-017-9866-y

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

Pedro Machado Manhães de Castro ¹ Olivier Devillers ²

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

Type de document :

Article dans une revue

Discrete and Computational Geometry, Springer Verlag, 2018, 60 (1), pp.200--219. 〈10.1007/s00454-017-9866-y〉

Domaine :

Informatique [cs] / Géométrie algorithmique [cs.CG]

Liste complète des métadonnées

Littérature citée [2 références] Voir Masquer Télécharger

https://hal.inria.fr/hal-01477030
Contributeur : Olivier Devillers <>
Soumis le : dimanche 26 février 2017 - 19:32:49
Dernière modification le : mardi 31 juillet 2018 - 15:00:02
Document(s) archivé(s) le : samedi 27 mai 2017 - 12:33:05

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

Fichiers

Identifiants

Collections

Citation

Exporter

Métriques

410

91

Contact

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

Fichiers

Identifiants

Collections

Citation

Exporter

Partager

Métriques

410

91

Contact