Next: Problem 65: Magic Configurations
Previous: Problem 63: Dynamic Planar Nearest Neighbors
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.
George Hart and Joseph O’Rourke, 2004.
Open.
More general problems seem even more difficult.
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].
Problem 9: Edge-Unfolding Convex Polyhedra.
Problem 42: Vertex-Unfolding Polyhedra.
Problem 43: General Unfolding of Nonconvex Polyhedra.
folding and unfolding; polyhedra
J. O’Rourke, 14 Jul 2006, 16 Jul 2007.
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.
Erik D. Demaine and Joseph O’Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, July 2007. http://www.gfalop.org.
Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2004. In Proc. 17th Canad. Conf. Comput. Geom., pages 303–306, 2005.
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.