Nonobtuse triangulations of PSLGs

Abstract

We show that any planar straight line graph (PSLG) with $n$ vertices has a conforming triangulation by $O(n^{2.5})$ nonobtuse triangles (all angles $\le 90^{\circ }$), answering the question of whether any polynomial bound exists. A nonobtuse triangulation is Delaunay, so this result also improves a previous $O(n^3)$ bound of Eldesbrunner 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^2)$ triangles are needed, improving an $O(n^4)$ bound of Bern and Eppstein. We also show that for any $\epsilon >0$, every PSLG has a conforming triangulation with $O(n^2/{\epsilon }^2)$ elements and with all angles bounded above by $90^{\circ }+\epsilon$. This improves a result of S. Mitchell when $\epsilon =3\pi /8=67.5^{\circ }$ and Tan when $\epsilon =7\pi /30=42^{\circ }$.

65 pages, 46 figures

References in corpus (1)

• Quadrilateral meshes for PSLGs

Cited by in corpus (1)

• Quadrilateral meshes for PSLGs