An upper bound for conforming Delaunay triangulations
Herbert Edelsbrunner, Tiow-Seng Tan · 1992
A plane geometric graph C in R2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that for every G with n vertices and m edges, there is a completion of a Delaunay triangulation of O(m2n) points that conforms to G. The algorithm that constructs the points is also described.