On the difficulty of triangulating three-dimensional nonconvex polyhedra (Q1182990)

It is well known that for a given 3-dimensional nonconvex polyhedron a decomposition into tetrahedra without additional vertices (= a triangulation) is not always possible. A twisted prism provides a counter-example. The authors consider the algorithmic question how to decide whether a given 3-dimensional polyhedron \(P\) is triangulable or not. It turns out that this problem is \(NP\)-complete even when restricted to the case of star-shaped polyhedra. More precise it is shown that for each Boolean expression \(E\) there is a polyhedron \(P\) such that \(E\) is satisfiable iff \(P\) can be triangulated. The construction of such a \(P\) makes use of so-called ``niches'' which are twisted prisms attached to a given polyhedron and which restrict the possible triangulations in a very effective and controllable way. If one allows additional vertices (Steiner points) then the problem turns out to be \(NP\)-hard if the number of such points is at most \(c\cdot n^{3/2}\) for an \(n\)-vertex polyhedron.