Problem 43: General Unfoldings of Nonconvex Polyhedra

Statement

Can every polyhedron without boundary (every edge is incident to exactly two facets) 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 recently vertex-unfoldings (see Problem 42).

Origin

Likely [BDE+03]

Status/Conjectures

Open.

Partial and Related Results

It is known that every convex polyhedron has a general unfolding. In fact, there are two general methods for unfolding convex polyhedra: the star unfolding [AO91,AAOS97] and the source unfolding [MMP87].

On the nonconvex side, Biedl et al. [BDD+98] demonstrate general unfoldings for two large classes of orthogonal polyhedra. Bern et al. [BDE+03] show a general unfolding for a simplicial polyhedron (whose faces are all triangles) that has no edge unfolding, establishing that general unfoldings are more powerful than edge unfoldings.

Related Open Problems

Problem 9: Edge-Unfolding Convex Polyhedra.
Problem 42: Vertex-Unfolding Polyhedra.

Appearances

[BDE+03]

Categories

folding and unfolding; polyhedra

Entry Revision History

E. Demaine, 7 Aug. 2002.

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.

MMP87

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