On triangulating three-dimensional polygons

A three-dimensional polygon is triangulable if it has a non-self-intersecting triangulation which defines a simply-connected 2-manifold. We show that the problem of deciding whether a 3-dimensional polygon is triangulable is Np-complete, We then establish some necessary conditions and some sufficient conditions for a polygon to be triangulable, providing special cases when the decision problem may be answered in polynomial time, (C) 1998 Elsevier Science B.V.