next up previous
Next: Problem 44: 3-Colorability of Up: The Open Problems Project Previous: Problem 42: Vertex-Unfolding Polyhedra


Problem 43: General Unfoldings of Nonconvex Polyhedra

Statement
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).
Origin
Perhaps [BDE+03].
Status/Conjectures
Open.
Partial and Related Results
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.

Related Open Problems
Problem 9: Edge-Unfolding Convex Polyhedra.
Problem 42: Vertex-Unfolding Polyhedra.
Appearances
[BDE+03], [DO07a, Open Prob. 22.3].
Categories
folding and unfolding; polyhedra
Entry Revision History
E. Demaine, 7 Aug. 2002; J. O'Rourke, 24 Jul 2008.

Bibliography

AAOS97
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.

AO91
Boris Aronov and Joseph O'Rourke.
Nonoverlap of the star unfolding.
In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 105-114, 1991.

BDD+98
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.

BDE+03
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.

DFO07
Mirela Damian, Robin Flatland, and Joseph O'Rourke.
Epsilon-unfolding orthogonal polyhedra.
Graphs and Combinatorics, 23[Suppl]:179-194, 2007.
Akiyama-Chvátal Festschrift.

DO07a
Erik D. Demaine and Joseph O'Rourke.
Geometric Folding Algorithms: Linkages, Origami, Polyhedra.
Cambridge University Press, July 2007.
http://www.gfalop.org.

IOV07
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].

MMP87
Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou.
The discrete geodesic problem.
SIAM J. Comput., 16:647-668, 1987.

O'R08
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.


next up previous
Next: Problem 44: 3-Colorability of Up: The Open Problems Project Previous: Problem 42: Vertex-Unfolding Polyhedra
The Open Problems Project - December 04, 2015