I would like to know is there a way to break a concave polyhedron into a few convex polyhedron?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ 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 $\endgroup$– Yemon ChoiCommented Oct 10, 2010 at 4:24
-
1$\begingroup$ 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... $\endgroup$– sleepless in beantownCommented Oct 10, 2010 at 4:34
-
$\begingroup$ 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. $\endgroup$– Kevin O'BryantCommented Oct 10, 2010 at 16:55
-
3$\begingroup$ 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" $\endgroup$– Yemon ChoiCommented Oct 10, 2010 at 20:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Oct 10, 2010 at 14:55
-
1$\begingroup$ The link to
sciencedirect.comis broken, but the article can be found at doi:10.1016/S0925-7721(96)00024-7 (Zbl 1133.52305). $\endgroup$ Commented May 11, 2023 at 14:39
$\begingroup$
$\endgroup$
10
Take all planes of the facets of your polyhedron $P$. They divide the space onto (open) convex regions. Each of them either is contained in $P$, or does not have common points with $P$. Take those regions which are contained in $P$ (or their closures, if you prefer).
answered Oct 10, 2010 at 6:25
-
$\begingroup$ I don't think it's obvious that the intersection of a convex set with the nonconvex polyhedron is itself convex. $\endgroup$ Commented Oct 10, 2010 at 16:52
-
$\begingroup$ @Kevin It is either empty or itself, hence convex $\endgroup$ Commented Oct 10, 2010 at 16:54
-
$\begingroup$ 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. $\endgroup$ Commented Oct 10, 2010 at 18:31
-
$\begingroup$ 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 . $\endgroup$ Commented Oct 10, 2010 at 18:46
-
1$\begingroup$ @Joseph yes, that's my point exactly sorry for being not clear $\endgroup$ Commented Oct 10, 2010 at 18:55