Nonobtuse Triangulations of PSLGs

We show that any planar straight line graph with n vertices has a conforming triangulation by nonobtuse triangles (all angles ), answering the question of whether any polynomial bound exists. A nonobtuse triangulation is Delaunay, so this result also improves a previous bound of Edelsbrunner and Tan for conforming Delaunay triangulations of PSLGs. In the special case that the PSLG is the triangulation of a simple polygon, we will show that only triangles are needed, improving an bound of Bern and Eppstein. We also show that for any , every PSLG has a conforming triangulation with elements and with all angles bounded above by . This improves a result of S. Mitchell when and Tan when Tan when epsilon = 7/30 pi = 42 degrees.