2011/03/31 by Ge Xia · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Topological and Geometric Data Analysis #cs.CG
paper · pdf · doi:10.1137/110832458
published as SIAM Journal on Computing, 42(4), 1620-1659, 2013 · 41 pages, 16 figures. A preliminary version of this paper appeared in the Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG 2011). This is a revised version of the previous preprint [v1]
openalex publication_date 2013/01/01 · arxiv created 2013/06/04 · arxiv updated 2013/08/30 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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 ρ = 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.