next up previous
Next: Problem 65: Magic Configurations Up: The Open Problems Project Previous: Problem 63: Dynamic Planar


Problem 64: Edge-Unfolding Polycubes

Statement
Is there any genus-zero orthogonal polyhedron P built by gluing together cubes face-to-face that cannot be edge-unfolded, where all cube edges on the surface of P are considered edges available for cutting? These orthogonal polyhedra are sometimes known as polycubes, 3D versions of 2D polyominoes.
Origin
George Hart and Joseph O'Rourke, 2004.
Status/Conjectures
Open.
Motivation
More general problems seem even more difficult.
Partial and Related Results
This is a special case of a more general problem, which is equally open. The goal, as in Problem 9, is to cut the surface and unfold without overlap. An edge unfolding only permits cutting along edges of the polyhedron. A grid unfolding adds extra edges to the surface by intersecting the polyhedron with planes parallel to coordinate planes through every vertex, and so is easier to edge-unfold. Easier still is the posed problem: The orthogonal polyhedron is built from cubes, and all cube edges are available for cutting. Is there any such polyhedron that cannot be edge-unfolded? Such an example would narrow the options, but it may be that every orthogonal polyhedron can be grid-unfolded. (An easy box-on-box example [BDD+98] shows that without some surface refinement [DO05], not all orthogonal polyhedra can be edge-unfolded.) The posed question is among the most specific whose answer would make progress.

Only a few narrow subclasses of orthogonal polyhedra are known to have grid-unfolding algorithms: orthotubes, orthostacks of orthogonally convex slabs, and orthogonal terrains. See [O'R08].

Related Open Problems
Problem 9: Edge-Unfolding Convex Polyhedra.
Problem 42: Vertex-Unfolding Polyhedra.
Problem 43: General Unfolding of Nonconvex Polyhedra.
Appearances
[DO07b]
Categories
folding and unfolding; polyhedra
Entry Revision History
J. O'Rourke, 14 Jul 2006, 16 Jul 2007.

Bibliography

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.

DO07b
Erik D. Demaine and Joseph O'Rourke.
Geometric Folding Algorithms: Linkages, Origami, Polyhedra.
Cambridge University Press, 2007.
In press. http://www.gfalop.org (formerly http://www.fucg.org).

DO05
Erik D. Demaine and Joseph O'Rourke.
Open problems from CCCG 2004.
In Proc. 17th Canad. Conf. Comput. Geom., pages 303-306, 2005.

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 65: Magic Configurations Up: The Open Problems Project Previous: Problem 63: Dynamic Planar
The Open Problems Project - December 04, 2015