Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2016

Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation

Bornes sur l'élongation du plus court chemin dans la triangulation de Delaunay d'un processus de Poisson de grande densité

(1) , (2)
1
2

Abstract

Let $X:=X_n\cup\{(0,0),(1,0)\}$, where $X_n$ is a planar Poisson point process of intensity $n$. We prove that the distance between the expected length of the shortest path between $(0,0)$ and $(1,0)$ in the Delaunay triangulation associated with $X$ belongs to $[1+2.47\cdot 10^{-11}, 1.182]$ when the intensity of $X_n$ goes to infinity. Experimental values indicate that the correct value is about 1.04. We also prove that the expected number of Delaunay edges crossed by the line segment $[(0,0),(1,0)]$ is $\frac{64}{3\pi^2}\sqrt{n}+O(1)\simeq2.16\sqrt{n}$. Simulation code and Maple sheet are available with the research report.
Soit $X:=X_n\cup\{(0,0),(1,0)\}$, où $X_n$ est un processus ponctuel de Poisson planaire d'intensité $n$. Nous montrons que la longueur du plus court chemin entre $(0,0)$ et $(1,0)$ dans la triangulation de Delaunay de $X$ est dans l'intervalle $[1+2.47\cdot 10^{-11}, 1.182]$ quand $n$ tends vers l'infini. Les résultats expérimentaux indiquent que la valeur correcte est 1.04. Nous montrons aussi que l'espérance du nombre d'arêtes de Delaunay coupées par le segment $[(0,0),(1,0)]$ est $\frac{64}{3\pi^2}\sqrt{n}+O(1)\simeq2.16\sqrt{n}$. Le code pour les simulations et la feuille de calcul Maple sont disponibles avce ce rapport de recherche.
Fichier principal
Vignette du fichier
RR-8935.pdf (4.11 Mo) Télécharger le fichier
Vignette du fichier
vignette.png (31.72 Ko) Télécharger le fichier
Vignette du fichier
maple.zip (26.83 Ko) Télécharger le fichier
Vignette du fichier
simulation.zip (3.67 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01346203 , version 1 (18-07-2016)

Identifiers

Cite

Nicolas Chenavier, Olivier Devillers. Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation. [Research Report] RR-8935, Inria. 2016, pp.34. ⟨hal-01346203⟩
280 View
183 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More