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

2016/07/19 by Nicolas Chenavier, Chenavier, Nicolas, Olivier Devillers +1
Computer Science · Environmental Science · Mathematics · #Computational Geometry and Mesh Generation #FOS: Mathematics #Point processes and geometric inequalities #Probability (math.PR) #Remote Sensing and LiDAR Applications

paper · pdf · doi:10.48550/arxiv.1607.05770

openalex publication_date 2016/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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. 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 equivalent to 2.16√(n) and that the expected length of a particular path converges to 1.18 giving an upper bound on the stretch factor.

Related

• The Stretch Factor of L₁- and L_∞-Delaunay Triangulations
• The Stretch Factor of Hexagon-Delaunay Triangulations
• The dilation of the Delaunay triangulation is greater than π/2
• On the Stretch Factor of Convex Delaunay Graphs
• Longest increasing path within the critical strip