On the Stretch Factor of the Constrained Delaunay Triangulation
Prosenjit K. Bose · 2006
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 isin P, we show that there exists a path from p to q in CDT(P, S), denoted SPCDT(p, q) such that every edge in the path has length at most \pq\ and the ratio \SPCDT(p, q)|/|pq| is at most 4piradic3/9 (ap 2.42), thereby improving on the previously known bound of pi(ap1+radic5)/2 (ap5.08).