Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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
1  
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
3  
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

2 Answers 2

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.

share|improve this answer

Take all planes of facets of your polyhedron. They divide the space onto convex sets. Each of them either is contained to your polyhedron, or does not meet it at all. Take those which are contained.

share|improve this answer
    
I don't think it's obvious that the intersection of a convex set with the nonconvex polyhedron is itself convex. –  Kevin O'Bryant Oct 10 '10 at 16:52
    
@Kevin It is either empty or itself, hence convex –  Fedor Petrov Oct 10 '10 at 16:54
    
Fedor, I just drew a nonconvex polygon P in the plane, attempting to cause one of your convex sets C to be part inside and part outside the original P. It was easy, I count 14 edges, with C a certain triangle. Putting in a malicious bend at the right place, making 15 edges, the intersection of C with P is not convex either. Anyway, the number of edges is nearly irrelevant, as I forced the bad intersection first, then filled in the rest. P resembles a capital letter C with teeth. –  Will Jagy Oct 10 '10 at 18:31
    
The way I understood Fedor's suggestion is to form the arrangement determined by all the planes containing faces of the polyhedron. Each cell of the arrangement is convex, and is either inside or outside the polyhedron. Here the term "arrangement" is defined at en.wikipedia.org/wiki/Arrangement_of_planes . –  Joseph O'Rourke Oct 10 '10 at 18:46
1  
@Joseph yes, that's my point exactly sorry for being not clear –  Fedor Petrov Oct 10 '10 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.