(Presented at the 12th Ann. ACM Symp. on Computational Geometry, Philadelphia, PA, 5/96; to appear in Computational Geometry: Theory and Applications)

On Triangulating Three-Dimensional Polygons

Gill Barequet¹, Matthew Dickerson², and David Eppstein³

¹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

Abstract

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.