Stretch Factor in a Planar Poisson-Delaunay Triangulation with a Large Intensity

Nicolas Chenavier 1 Olivier Devillers 2
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 := X_n ∪ \{(0, 0), (1, 0)\}$, where $X_n$ is a planar Poisson point process of intensity $n$. We provide a first non-trivial lower bound for the distance between the expected length of the shortest path between (0, 0) and (1, 0) in the Delaunay triangulation associated with $X$ when the intensity of $X_n$ goes to infinity. Simulations indicate that the correct value is about 1.04. We also prove that the expected length of the so-called upper path converges to $35/3\pi^2$, giving an upper bound for the expected length of the smallest path.
Type de document :
Article dans une revue
Advances in Applied Probability, Applied Probability Trust, 2018, 50 (1), pp.1-30. 〈http://www.appliedprobability.org/content.aspx?Group=journals&Page=apjournals〉
Liste complète des métadonnées

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


https://hal.inria.fr/hal-01700778
Contributeur : Olivier Devillers <>
Soumis le : lundi 5 février 2018 - 11:35:16
Dernière modification le : vendredi 16 février 2018 - 17:00:57

Fichiers

AP16381.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01700778, version 1

Collections

Citation

Nicolas Chenavier, Olivier Devillers. Stretch Factor in a Planar Poisson-Delaunay Triangulation with a Large Intensity. Advances in Applied Probability, Applied Probability Trust, 2018, 50 (1), pp.1-30. 〈http://www.appliedprobability.org/content.aspx?Group=journals&Page=apjournals〉. 〈hal-01700778〉

Partager

Métriques

Consultations de la notice

33

Téléchargements de fichiers

17