Stretch Factor of Long Paths in a planar Poisson-Delaunay Triangulation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 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é

Résumé

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
maple.zip (26.83 Ko) Télécharger le fichier
simulation.zip (3.67 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
299 Consultations
195 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More