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. American Mathematical Society, 2008.
To appear.