On triangulating three-dimensional polygons
Gill Barequet, Matthew T. Dickerson, David Eppstein · Computational Geometry · 1998
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.