THE STRETCH FACTOR OF THE DELAUNAY TRIANGULATION IS LESS THAN 1.998
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 parallel to pq parallel to. Proving a tight bound on the stretch factor of the Delaunay triangulation has been a long-standing open problem in computational geometry. In this paper we prove that the stretch factor of the Delaunay triangulation is less than rho = 1.998, significantly improving the current best upper bound of 2.42 by Keil and Gutwin ["The Delaunay triangulation closely approximates the complete Euclidean graph," in Proceedings of the 1st Workshop on Algorithms and Data Structures (WADS), 1989, pp. 47-56]. Our bound of 1.998 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). Our result has a direct impact on the problem of constructing spanners of Euclidean graphs, which has applications in the area of wireless computing.
stretch factor delaunay triangulation dilation spanning ratio spanners