- On triangulating three-dimensional polygons.
G. Barequet, M. Dickerson, and D. Eppstein.
12th ACM Symp. Comp. Geom., Philadelphia, 1996, pp. 38–47.
Comp. Geom. Theory & Applications 10: 155–170, 1998.It is NP-complete, given a simple polygon in 3-space, to find a triangulated simply-connected surface (without extra vertices) spanning that polygon. If extra vertices are allowed, or the surface may be curved, such a surface exists if and only if the polygon is unknotted; the complexity of testing knottedness remains open. Snoeyink has shown that exponentially many extra vertices may be required for a triangulated spanning disk.