Optimal bound for conforming quality triangulations

Abstract

This paper shows that for any plane geometric graph G with n vertices, there exists a triangulation T conforms to G, i.e. each edge of G is the union of some edges of T, where T has O(n2) vertices with angles of its triangles measuring no more than 11/15 π. Additionally, T can be computed in O(n2 log n) time. The quadratic bound on the size of its vertex set is within a constant factor of worst case optimal.