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

2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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.
Keywords :
Document type :
Reports
Domain :

Cited literature [17 references]

https://hal.inria.fr/hal-01346203
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Monday, July 18, 2016 - 2:44:57 PM
Last modification on : Thursday, November 25, 2021 - 8:22:29 AM

### Files

RR-8935.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-01346203, version 1
• ARXIV : 1607.05770

### Citation

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⟩

### Metrics

Les métriques sont temporairement indisponibles