**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.

(SCG paper – Full paper)

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.