An optimal bound for high-quality conforming triangulations

Abstract

This paper shows that, for any plane geometric graph with G n vertices, there is a triangulation τ that conforms to G, i.e., each edge of G is the union of some edges of τ, where τ has O(n2) vertices with each angle of its triangles measuring no more than 11/15π. Additionally, τ can be computed in O(n2 log n) time.