Polyhedron Decomposition

From CGAFaq

Usually this problem is interpreted as seeking a collection of pairwise disjoint convex polyhedra whose set union is the original polyhedron . The following facts are known about this difficult problem:

• Not every polyhedron may be partitioned by diagonals into tetrahedra. A counterexample is due to Schönhardt [ORourke:1987, p.254]
• Determining whether a polyhedron may be so partitioned is NP--hard, a result due to Seidel and Ruppert [Ruppert:1992].
• Removing the restriction to diagonals, i.e., permitting so--called Steiner points, there are polyhedra of vertices that require convex pieces in any decomposition. This was established by Chazelle, [Chazelle:1984]. See also [ORourke:1987, p.256].
• An algorithm of Palios and Chazelle guarantees at most pieces, where is the number of reflex edges (i.e., grooves), [Chazelle:1990].
• Barry Joe's geompack package, at http://members.allstream.net/~bjoe/ includes a 3D convex decomposition Fortran program.
• There seems to be no other publicly available code.