Important Notice: Our web hosting provider recently started charging us for additional visits, which was unexpected. In response, we're seeking donations. Depending on the situation, we may explore different monetization options for our Community and Expert Contributors. It's crucial to provide more returns for their expertise and offer more Expert Validated Answers or AI Validated Answers. Learn more about our hosting issue here.

Subject 5.20: How can I decompose a polyhedron into convex pieces?

0
Posted

Subject 5.20: How can I decompose a polyhedron into convex pieces?

0

Usually this problem is interpreted as seeking a collection of pairwise disjoint convex polyhedra whose set union is the original polyhedron P. The following facts are known about this difficult problem: • Not every polyhedron may be partitioned by diagonals into tetrahedra. A counterexample is due to Scho:nhardt [O’Rourke (A), p.254]. • Determining whether a polyhedron may be so partitioned is NP-hard, a result due to Seidel & Ruppert [Disc. Comput. Geom. + 7(3) 227-254 (1992).] • Removing the restriction to diagonals, i.e., permitting so-called Steiner points, there are polyhedra of n vertices that require n^2 convex pieces in any decomposition. This was established by Chazelle [SIAM J. Comput. 13: 488-507 (1984)]. See also [O’Rourke (A), p.256] • An algorithm of Palios & Chazelle guarantees at most O(n+r^2) pieces, where r is the number of reflex edges (i.e., grooves). [Disc. Comput. Geom. 5:505-526 (1990).] • Barry Joe’s geompack package, at ftp://ftp.cs.ualberta.ca/pub/geompack, i

Related Questions

Thanksgiving questions

*Sadly, we had to bring back ads too. Hopefully more targeted.