The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
Ge Xia · SIAM Journal on Computing · 2013
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||$. 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.