¹Center for Geometric Computing Department of Computer Science Johns Hopkins University Baltimore, MD 21218 barequet@cs.jhu.edu |
²Dept. of Mathematics and Computer Science Middlebury College Middlebury, VT 05753 dickerso@middlebury.edu |
³Dept. of Information and Computer Science University of California Irvine, CA 92717 eppstein@ics.uci.edu |

A three-dimensional polygon istriangulableif 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 isNP-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.