The stretch factor of the Delaunay triangulation is less than 1.998 (Q2862205)

Let \(S\) be a finite set of points in the Euclidean plane. Let \(D\) be a Delaunay triangulation of \(S\). The stretch factor (also known as dilation or spanning ratio) of \(D\) is the maximum ratio, among all points \(p\) and \(q\) in \(S\), of the shortest path distance from \(p\) to \(q\) in \(D\) over the Euclidean distance \(||pq||\). The problem of computing a tight bound on the stretch factor of the Delaunay triangulation has been an important open problem in computational geometry. In this paper, it is proved that the stretch factor of the Delaunay triangulation is less than \(\rho=1.998\). This bound improves the current best upper bound of \(2.42\) (see [\textit{J. M. Keil} and \textit{C. A. Gutwin}, Algorithms and data structures, Proc. workshop WADS '89, Ottawa/Canada 1989, Lect. Notes Comput. Sci. 382, 47--56 (1989; Zbl 0766.52004)]). The bound obtained also improves the upper bound of the best stretch factor that can be achieved by a plane spanner of a Euclidean graph (the current best upper bound is \(2\)).