We give an algorithm for triangulating n-vertex polygonal regions (with holes) so that no angle in the final triangulation measures more than π/2. The number of triangles in the triangulation is only O(n), improving a previous bound of O(n2), and the worst-case running time is O(nlog2n). The basic technique used in the algorithm, recursive subdivision by disks, is new and may have wider application in mesh generation. We also report on an implementation of our algorithm.

A number of different polyhedral decomposition problems have previously been studied, most notably the problem of triangulating a simple polygon. We are concerned with the tetrahedralization problem: decomposing a 3-dimensional polyhedron into a set of non-overlapping tetrahedra whose vertices are chosen from the vertices of the polyhedron. It has previously been shown that some polyhedra cannot be tetrahedralized in this fashion. We show that the problem of deciding whether a given polyhedron can be tetrahedralized is NP-complete, and hence likely to be computationally intractable. The problem remains NP-complete when restricted to the case of star-shaped polyhedra. Various versions of the question of how many Steiner points are needed to tetrahedralize a polyhedron also turn out to be NP-complete.