Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) (Q621930): Difference between revisions

The authors establish new lower bounds for the stretch factor of the Delaunay triangulation of points in the plane. Consider a 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. The stretch factor of \(T\) is, among all pairs \(p,q\) of points in \(P\), the maximum ratio of the length of the shortest path from \(p\) to \(q\) in \(P\) over the Euclidean distance \(|pq|\). It has long been conjectured that the stretch factor in \(T\) of any pair \(p,p'\in 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 \(\pi/2\approx1.5708\). In this paper, the authors show how to construct point sets in convex position with stretch factor \(>1.5810\) and in general position with stretch factor \(>1.5846\). Furthermore, it is shown 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. The best upper bound known for the stretch factor is \(\frac{2\pi}{3\cos(\frac\pi6)}\approx 2.419\) and was presented by \textit{J. M. Keil} and \textit{C. A. Gutwin} [Lect. Notes Comput. Sci. 382, 47--56 (1989; Zbl 0766.52004)] whereas for points in convex position it is \(2.33\) [cf., \textit{S. Cui}, \textit{I. A. Kanj} and \textit{G. Xia}, Comput. Geom. 44, No. 2, 104--109 (2011; Zbl 1217.65046)].