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 CDT(p, q). such that every edge in the path has length at most |pq| and the ratio |SPCDT(p, q)|/|pq| is at most 4π√3/9(≈ 2.42), thereby improving on the previously known bound of π(1+√5/2 (≈ 5.08).
|Keywords||Computational geometry, Constrained Delaunay triangulation, Spanner, Spanning ratio, Stretch factor|
|Conference||3rd International Symposium on Voronoi Diagrams in Science and Engineering 2006, ISVD 2006|
Bose, P, & Mark Keil, J. (2006). On the stretch factor of the constrained delaunay triangulation. Presented at the 3rd International Symposium on Voronoi Diagrams in Science and Engineering 2006, ISVD 2006. doi:10.1109/ISVD.2006.28