TRIANGULATING POLYGONS WITHOUT LARGE ANGLES

We show how to triangulate polygonal regions-adding extra vertices as necessary-with triangles of guaranteed quality. Using only O(n) triangles, we can guarantee that the smallest height (shortest dimension) of a triangle in a triangulation of an n-vertex polygon (with holes) is a constant fraction of the largest possible. Using O(n log n) triangles for simple polygons or O(n(3/2)) triangles for polygons with holes, we can guarantee that the largest angle is no greater than 150 degrees. We can add the guarantee on smallest height to these no-large-angle results, without increasing the asymptotic complexity of the triangulation. Finally we give a nonobtuse triangulation algorithm for convex polygons that uses O(n(1.85)) triangles.