On the Stretch Factor of the Constrained Delaunay Triangulation

摘要

Given a set P of n points in the plane and a set S of non-crossing line segments whose endpoints are in P, let CDT(P, S) be the constrained Delaunay triangulation of P with respect to S. Given any two visible points p, q∈P, we show that there exists a path from p to q in CDT(P, S), denoted SP{sub}(CDT)(p, q), such that every edge in the path has length at most |pq| and the ratio |SP{sub}(CDT)(p, q)|/|pq| is at most 4π3{sup}(1/2)/9 (≈ 2.42), thereby improving on the previously known bound of π(1+5{sup}(1/2))/2(≈ 5.08).