Welcome to MathOverflow

Question

1

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

edited Oct 10 2010 at 16:55

Kevin O'Bryant
6,442●1●27●54

asked Oct 10 2010 at 3:59

unknown (google)
11●1

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 2010 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 2010 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 2010 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 2010 at 20:52

Joseph O'Rourke · Answer 1 · 2010-10-10 14:55:40Z UTC

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.

Fedor Petrov · Answer 2 · 2010-10-10 06:25:18Z UTC

6

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.

answered Oct 10 2010 at 6:25

Fedor Petrov
6,789●1●12●38

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 2010 at 16:52

@Kevin It is either empty or itself, hence convex – Fedor Petrov Oct 10 2010 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 2010 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 2010 at 18:46

1

@Joseph yes, that's my point exactly sorry for being not clear – Fedor Petrov Oct 10 2010 at 18:55

show 5 more comments

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.