Nonobtuse Triangulations of PSLGs

We show that any planar straight line graph with n vertices has a conforming triangulation by O(n^2.5) nonobtuse triangles (all angles ≤ 90 ^∘), answering the question of whether any polynomial bound exists. A nonobtuse triangulation is Delaunay, so this result also improves a previous O(n³) 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 O(n²) triangles are needed, improving an O(n⁴) bound of Bern and Eppstein. We also show that for any ε> 0 , every PSLG has a conforming triangulation with O(n²/ ε²) elements and with all angles bounded above by 90 ^∘+ ε. This improves a result of S. Mitchell when ε=38π=67.5∘ and Tan when ε=730π=42∘.