Newsgroups: comp.graphics.algorithms
Subject: Re: convex decomposition of 3D polyhedra
From: orourke@grendel.csc.smith.edu (Joseph O'Rourke)
Date: 15 May 97 18:51:47 GMT

In article <3379E9D0.51BF@usc.edu>, Steven Spitz  <spitz@usc.edu> wrote:
>Is there any available code to produce a convex decomposition of a 3D
>polyhedra?  [...]
>
>Any pointers to relevant literature are also welcome, and please send 
>e-mail, too.

This is all I can provide.  The first paper below proves that you might
need n^2 pieces for a polyhedron of n vertices.  The second includes
the previously-known fact that partitions into tetrahedra are not
always possible, and proves that deciding whether this is possible
is NP-complete.

@inproceedings{c-cdp-81
, author =      "B. Chazelle"
, title =       "Convex decompositions of polyhedra"
, booktitle =   "Proc. 13th Annu. ACM Sympos. Theory Comput."
, year =        1981
, pages =       "70--79"
}
@article{rs-dttdn-92
, author =      "J. Ruppert and R. Seidel"
, title =       "On the difficulty of triangulating three-dimensional non-convexpolyhedra"
, journal =     "Discrete Comput. Geom."
, volume =      7
, year =        1992
, pages =       "227--253"
}