NONOBTUSE TRIANGULATIONS OF PSLGS
Christopher J. Bishop · 2010
Abstract. We show that any planar PSLG with n vertices has a conforming triangulation by O(n2.5) nonobtuse triangles; they may be chosen to be all acute or all right. This result also improves a previous O(n3) bound of Eldesbrunner and Tan for conforming Delaunay triangulations. In the special case that the PSLG is the triangulation of a simple polygon, we will show that only O(n2) elements are needed, improving an O(n4) bound of Bern and Eppstein. We also show that for any ǫ> 0, every PSLG has a conforming triangulation with O(n2 /ǫ2) elements and with all angles bounded above by 90 ◦ +ǫ. This improves a result of S. Mitchell when ǫ = 3 8π = 67.5 ◦ and Tan when ǫ = 7 30π = 42 ◦. Finally, we prove that any PSLG has a conforming quadrilateral mesh with O(n2) elements and all new angles between 60 ◦ and 120 ◦ (the complexity and angle bounds are both sharp). Moreover, all but O(n) of the angles may be taken in a smaller interval, say [89◦,91 ◦].