# How to break a concave polyhedron into a few convex polyhedron?

I would like to know is there a way to break a concave polyhedron into a few convex polyhedron?

• In certain cases yes, In general, I don't know. Could you please provide some evidence/illustration that you've thought about this, and some indication of why you want to know? Otherwise the way you phrase the question makes it sound like idle curiosity – Yemon Choi Oct 10 '10 at 4:24
• What have you tried so far to attack this problem? Have you tried to break down a concave polygon into its component convex polygons? How are you specifying the polyhedron... – sleepless in beantown Oct 10 '10 at 4:34
• Just the fact that it can be broken down (triangulated) is not as obvious as it seems at first glance. This seems to me to be roughly equivalent to the Jordan curve theorem, so I'd beware any answer that is both simple and doesn't use Jordan's result. And then there's that pesky adjective you used: "few". Nice problem. – Kevin O'Bryant Oct 10 '10 at 16:55
• It may be a nice problem, but I still wish the original post had communicated more than "here's something I don't know, let me know when you guys have the answer" – Yemon Choi Oct 10 '10 at 20:52

The problem of partitioning a polyhedron into the minimum possible number of convex pieces is NP-hard. Bernard Chazelle established a quadratic lower bound—$\Omega(n^2)$ in terms of the number $n$ of vertices—in the paper "Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm," SIAM Journal on Computing Volume 13 , Issue 3 (August 1984) pp. 488 - 507. He also provided a theoretical algorithm in that paper, perhaps never implemented. There has been subsequent work, e.g., "Strategies for polyhedral surface decomposition: An experimental study," Computational Geometry, Volume 7, Issues 5-6, April 1997, Pages 327-342.