Subject 5.20: How can I decompose a polyhedron into convex pieces?
Usually this problem is interpreted as seeking a collection of pairwise disjoint convex polyhedra whose set union is the original polyhedron P. The following facts are known about this difficult problem: • Not every polyhedron may be partitioned by diagonals into tetrahedra. A counterexample is due to Scho:nhardt [O’Rourke (A), p.254]. • Determining whether a polyhedron may be so partitioned is NP-hard, a result due to Seidel & Ruppert [Disc. Comput. Geom. + 7(3) 227-254 (1992).] • Removing the restriction to diagonals, i.e., permitting so-called Steiner points, there are polyhedra of n vertices that require n^2 convex pieces in any decomposition. This was established by Chazelle [SIAM J. Comput. 13: 488-507 (1984)]. See also [O’Rourke (A), p.256] • An algorithm of Palios & Chazelle guarantees at most O(n+r^2) pieces, where r is the number of reflex edges (i.e., grooves). [Disc. Comput. Geom. 5:505-526 (1990).] • Barry Joe’s geompack package, at ftp://ftp.cs.ualberta.ca/pub/geompack, i