POLYNOMIAL-SIZE NONOBTUSE TRIANGULATION
Marshall W. Bern, David Eppstein · 1992
We describe methods for triangulating polygonal regions of the plane so that no triangle has a large angle. Our main result is that a polygon with n sides can be triangulated with O(n 2 ) nonobtuse triangles. We also show that any triangulation (without Steiner points) of a simple polygon has a reflnement with O(n 4 ) nonobtuse triangles. Finally we show that a triangulation whose dual is a path has a reflnement with only O(n 2 ) nonobtuse triangles.