OP-01089 Open

General unfoldings of nonconvex polyhedra

A general unfolding of a closed polyhedron cuts its surface anywhere, not only along edges, and lays the surface out in the plane as one piece without overlap. This is in contrast with edge-unfoldings, which cut only along edges, and with vertex-unfoldings.

Every convex polyhedron has a general unfolding, by the star unfolding (Aronov and O'Rourke; Agarwal, Aronov, O'Rourke and Schevon), the source unfolding (Mitchell, Mount and Papadimitriou), or unfolding along a quasigeodesic (Itoh, O'Rourke and Vîlcu). Bern, Demaine, Eppstein, Kuo, Mantler and Snoeyink found a nonconvex polyhedron with triangular faces that has a general unfolding but no edge-unfolding; Biedl et al. had given such an example earlier with nonconvex faces. Damian, Flatland and O'Rourke showed that every orthogonal polyhedron has a general unfolding, though the piece may be exponentially long and thin.

Problem. Does every closed polyhedron have a general unfolding?

Source: Origin uncertain; perhaps Bern, Demaine, Eppstein, Kuo, Mantler and Snoeyink (2003); see also Demaine and O'Rourke (2007), Open Problem 22.3; Problem 43 of The Open Problems Project (Demaine, Mitchell and O'Rourke).

Imported from topp.openproblem.net.

Classification

Primary: MG — Metric Geometry
Secondary: CO
Keywords: general unfolding, nonconvex polyhedra, The Open Problems Project

References

@article{bern2003,
  author  = {Bern, Marshall and Demaine, Erik D. and Eppstein, David and Kuo, Eric and Mantler, Andrea and Snoeyink, Jack},
  title   = {Ununfoldable Polyhedra with Convex Faces},
  journal = {Comput. Geom. Theory Appl.},
  volume  = {24},
  number  = {2},
  year    = {2003},
  pages   = {51--62}
}

@inproceedings{aronov1991,
  author    = {Aronov, Boris and O'Rourke, Joseph},
  title     = {Nonoverlap of the star unfolding},
  booktitle = {Proc. 7th Annu. ACM Sympos. Comput. Geom.},
  year      = {1991},
  pages     = {105--114}
}

@article{agarwal1997,
  author  = {Agarwal, Pankaj K. and Aronov, Boris and O'Rourke, Joseph and Schevon, Catherine A.},
  title   = {Star Unfolding of a Polytope with Applications},
  journal = {SIAM J. Comput.},
  volume  = {26},
  year    = {1997},
  pages   = {1689--1713}
}

@article{mitchell1987,
  author  = {Mitchell, Joseph S. B. and Mount, David M. and Papadimitriou, Christos H.},
  title   = {The discrete geodesic problem},
  journal = {SIAM J. Comput.},
  volume  = {16},
  year    = {1987},
  pages   = {647--668}
}

@techreport{itoh2007,
  author        = {Itoh, Jin-ichi and O'Rourke, Joseph and V{\^i}lcu, Costin},
  title         = {Unfolding Convex Polyhedra via Quasigeodesics},
  institution   = {Smith College},
  number        = {085},
  year          = {2007},
  eprint        = {0707.4258},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/0707.4258v2}
}

@inproceedings{biedl1998,
  author    = {Biedl, Therese and Demaine, Erik D. and Demaine, Martin L. and Lubiw, Anna and O'Rourke, Joseph and Overmars, Mark and Robbins, Steve and Whitesides, Sue},
  title     = {Unfolding Some Classes of Orthogonal Polyhedra},
  booktitle = {Proc. 10th Canad. Conf. Comput. Geom.},
  year      = {1998},
  pages     = {70--71},
  url       = {https://erikdemaine.org/papers/CCCG98b/paper.ps}
}

@article{damian2007,
  author  = {Damian, Mirela and Flatland, Robin and O'Rourke, Joseph},
  title   = {Epsilon-Unfolding Orthogonal Polyhedra},
  journal = {Graphs and Combinatorics},
  volume  = {23},
  number  = {Suppl.},
  year    = {2007},
  pages   = {179--194}
}

@book{demaine2007gfalop,
  author    = {Demaine, Erik D. and O'Rourke, Joseph},
  title     = {Geometric Folding Algorithms: Linkages, Origami, Polyhedra},
  publisher = {Cambridge University Press},
  year      = {2007},
  url       = {https://gfalop.org/}
}

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-01089, "General unfoldings of nonconvex polyhedra", clopen.solutions.