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 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" }