an upper bound for conforming delaunay triangulations
A plane geometric graph C in R 2 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( m 2 n ) points that conforms to G . The algorithm that constructs the points is also described.
triangulation graph completeness point algorithm