Consider the Delaunay triangulation T of a set P of points in the plane as a Euclidean graph, in which the weight of every edge is its length. It has long been conjectured that the stretch factor in T of any pair p, p′ ∈P, which is the ratio of the length of the shortest path from p to p′ in T over the Euclidean distance ∥pp∥, can be at most φ/2 ≈ 1.5708. In this paper, we show how to construct point sets in convex position with stretch factor > 1.5810 and in general position with stretch factor > 1.5846. Furthermore, we show that a sufficiently large set of points drawn independently from any distribution will in the limit approach the worst-case stretch factor for that distribution.

Additional Metadata
Keywords Dilation, Point configuration, Shortest path, Spanning ratio
Persistent URL
Journal Computational Geometry
Bose, P, Devroye, L. (Luc), Löffler, M. (Maarten), Snoeyink, J. (Jack), & Verma, V. (Vishal). (2011). Almost all Delaunay triangulations have stretch factor greater than φ/2. Computational Geometry, 44(2), 121–127. doi:10.1016/j.comgeo.2010.09.009