Next: Problem 44: 3-Colorability of Arrangements of Great Circles
Previous: Problem 42: Vertex-Unfolding Polyhedra
Can every closed polyhedron be cut along its surface and unfolded into one piece in the plane without overlap? Such an unfolding is called a general unfolding to distinguish from edge-unfoldings (see Problem 9) and vertex-unfoldings (see Problem 42).
Perhaps [BDE+03].
Open.
It is known that every convex polyhedron has a general unfolding. In fact, there are three general methods for unfolding convex polyhedra: the star unfolding [AO91], [AAOS97], the source unfolding [MMP87], and unfolding via quasigeodesics [IOV07].
On the nonconvex side, Bern et al. [BDE+03] show a general unfolding for a nonconvex simplicial polyhedron (whose faces are all triangles) that has no edge unfolding, establishing that general unfoldings are more powerful than edge unfoldings. (This was known earlier [BDD+98] but with an example using nonconvex faces.)
It is now known that all orthogonal polyhedra (those with all edges parallel to coordinate axes) have a general unfolding [DFO07], although the resulting single piece can be exponentially thin and long. See [O'R08] for a survey of progress on orthogonal polyhedra.
Problem 9: Edge-Unfolding Convex Polyhedra.
Problem 42: Vertex-Unfolding Polyhedra.
folding and unfolding; polyhedra
E. Demaine, 7 Aug. 2002; J. O’Rourke, 24 Jul 2008.
Pankaj K. Agarwal, Boris Aronov, Joseph O’Rourke, and Catherine A. Schevon. Star unfolding of a polytope with applications. SIAM J. Comput., 26:1689–1713, 1997.
Boris Aronov and Joseph O’Rourke. Nonoverlap of the star unfolding. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 105–114, 1991.
Therese Biedl, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O’Rourke, Mark Overmars, Steve Robbins, and Sue Whitesides. Unfolding some classes of orthogonal polyhedra. In Proc. 10th Canad. Conf. Comput. Geom., pages 70–71, 1998. Full version in Elec. Proc.: http://cgm.cs.mcgill.ca/cccg98/proceedings/cccg98-biedl-unfolding.ps.gz.
Marshall Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, and Jack Snoeyink. Ununfoldable polyhedra with convex faces. Comput. Geom. Theory Appl., 24(2):51–62, 2003.
Mirela Damian, Robin Flatland, and Joseph O’Rourke. Epsilon-unfolding orthogonal polyhedra. Graphs and Combinatorics, 23[Suppl]:179–194, 2007. Akiyama-Chvátal Festschrift.
Erik D. Demaine and Joseph O’Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, July 2007. http://www.gfalop.org.
Jin-ichi Itoh, Joseph O’Rourke, and Costin Vîlcu. Unfolding convex polyhedra via quasigeodesics. Technical Report 085, Smith College, July 2007. arXiv:0707.4258v2 [cs.CG].
Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. The discrete geodesic problem. SIAM J. Comput., 16:647–668, 1987.
Joseph O’Rourke. Unfolding orthogonal polyhedra. In J.E. Goodman, J. Pach, and R. Pollack, editors, Proc. Snowbird Conference Discrete and Computational Geometry: Twenty Years Later, pages 307–317. American Mathematical Society, 2008.