On the difficulty of tetrahedralizing 3-dimensional non-convex polyhedra

ABSTRACT

A number of different polyhedral decomposition problems have previously been studied, most notably the problem of triangulating a simple polygon. We are concerned with the tetrahedralization problem: decomposing a 3-dimensional polyhedron into a set of non-overlapping tetrahedra whose vertices are chosen from the vertices of the polyhedron. It has previously been shown that some polyhedra cannot be tetrahedralized in this fashion. We show that the problem of deciding whether a given polyhedron can be tetrahedralized is NP-complete, and hence likely to be computationally intractable. The problem remains NP-complete when restricted to the case of star-shaped polyhedra. Various versions of the question of how many Steiner points are needed to tetrahedralize a polyhedron also turn out to be NP-complete.

REFERENCES

• 1: D. Avis and H. ElGindy. Triangulating simplicial point. sets in space. Discrete Cotnput. Geom.. 2:99- 111,1987.
• 2: C.L. Bajaj and T.K. Deg. Convex decompositions of simple polyhedra. Technical Report CSD-TR-833. Purdue Univ.. Dept. Comp. Sci., 1989.
• 3: Bernard Marie Chazelle, Computational geometry and convexity, 1980
• 4: B. Chazelle , L. Palios, Triangulating a non-convex polytype, Proceedings of the fifth annual symposium on Computational geometry, p.393-400, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73876]
• 5: K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Proceedings of the fourth annual symposium on Computational geometry, p.18-22, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73396]
• 6: J. Culberson and R. Reckhow. Covering polygons is hard. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 601-611. IEEE, 1988.
• 7: H. Edelsbrunner. F.P. Preparata, and D.B. West. Tetrahedrizing point sets in three dimensions. Technical Report UIUCDCS-R-86-1310, University of Rlinois, Dept. Comput. Sci., 1986.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 10: J. O'Rourke and K. Supowit. Some NP-hard polygon decomposition problems. IEEE Trans. Info. Th., IT- 29:181-190, 1983.
• 11: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 12: E. Schiinhardt. ober die Zerlegung von Dreieckspolyedern in Tetraeder. Math. Ann., 98:309-312, 1928.
• 13: Robert E. Tarjan , Christopher van Wyk, An O (n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal on Computing, v.17 n.1, p.143-178, Feb. 1988 [doi>10.1137/0217010]
• 14: B. Von Hohenbalken. Finding simplicial subdivisions of polytopes. Mathematical Programming, 21:233-

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing

General Terms:
Algorithms, Theory