Refining a triangulation of a planar straight-line graph to eliminate large angles

We show that any planar straight line graph (PSLG) with v vertices can be triangulated with no angle larger than 7π/8 by adding O(v²log v) Steiner points in O(v²log² v) time. We first triangulate the PSLG with an arbitrary constrained triangulation and then refine that triangulation by adding additional vertices and edges. We follow a lazy strategy of starting from an obtuse angle and exploring the triangulation in search of a sequence of Steiner points that will satisfy a local angle condition. Explorations may either terminate successfully (for example at a triangle vertex), or merge. Some PSLGs require Ω(v²) Steiner points in any triangulation achieving any largest angle bound less than π. Hence the number of Steiner points added by our algorithm is within a log v factor of worst case optimal. For most inputs the number of Steiner points and running time would be considerably smaller than in the worst case