We study the problem of folding a polyomino $P$ into a polycube $Q$ , allowing faces of $Q$ to be covered multiple times. First, we define a variety of folding models according to whether the folds (a) must be along grid lines of $P$ or can divide squares in half (diagonally and/or orthogonally), (b) must be mountain or can be both mountain and valley, (c) can remain flat (forming an angle of $18 0^{\circ}$ ), and (d) must lie on just the polycube surface or can have interior faces as well. Second, we give all the inclusion relations among all models that fold on the grid lines of $P$ . Third, we characterize all polyominoes that can fold into a unit cube, in some models. Fourth, we give a linear-time dynamic programming algorithm to fold a tree-shaped polyomino into a constant-size polycube, in some models. Finally, we consider the triangular version of the problem, characterizing which polyiamonds fold into a regular tetrahedron.

A preliminary extended abstract appears in the Proceedings of the 27th Canadian Conference on Computational Geometry.²

Communicated by Gill Barequet

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

1. Z. Abel, E. Demaine, M. Demaine, H. Matsui, G. Rote and R. Uehara , Common developments of several different orthogonal boxes, Proc. 23rd Canadian Conf. Computational Geometry (CCCG) (2011), paper 49. Google Scholar
2. O. Aichholzer, M. Biro, E. D. Demaine, M. Demaine, D. Eppstein, S. Fekete, A. Hesterberg, I. Kostitsyna and C. Schmidt , Folding polyominoes into (poly)cubes, Proc. 27th Canadian Conf. Computational Geometry (CCCG) (2015), pp. 101–106. Google Scholar
3. G. Aloupis, P. K. Bose, S. Collette, E. D. Demaine, M. L. Demaine, K. Douïeb, V. Dujmović, J. Iacono, S. Langerman and P. Morin , Common unfoldings of polyominoes and polycubes, Proc. 9th Int. Conf. Computational Geometry, Graphs & Applications (CGGA), LNCS, Vol. 7033 (2011), pp. 44–54. Google Scholar
4. N. Beluhov, Cube folding, https://nbpuzzles.wordpress.com/2014/06/08/cube-folding/ (2014). Google Scholar
5. N. M. Benbernou, E. D. Demaine, M. L. Demaine and A. Lubiw, Universal hinge patterns for folding strips efficiently into any grid polyhedron (2017). Google Scholar
6. N. M. Benbernou, E. D. Demaine, M. L. Demaine and A. Ovadya , Universal hinge patterns to fold orthogonal shapes, Origami5: Proc. 5th Int. Conf. Origami in Science, Mathematics and Education (A K Peters, 2010), pp. 405–420. Google Scholar
7. E. D. Demaine, M. L. Demaine, V. Hart, J. Iacono, S. Langerman and J. O’Rourke , Continuous blooming of convex polyhedra, Graphs and Combinatorics 27(3) (2011) 363–376. Web of Science, Google Scholar
8. E. D. Demaine, M. L. Demaine and J. S. B. Mitchell , Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami, Comput. Geom. Theor. Appl. 16(1) (2000) 3–21. Web of Science, Google Scholar
9. E. D. Demaine and J. O’Rourke , Geometric Folding Algorithms: Linkages, Origami, Polyhedra (Cambridge University Press, 2007). Google Scholar
10. D. Eppstein and E. Mumford , Self-overlapping curves revisited, Proc. 20th ACM-SIAM Symp. Discrete Algorithms (SODA) (2009), pp. 160–169. Google Scholar
11. A. Lubiw and J. O’Rourke, When can a polygon fold to a polytope? Technical Report 048, Smith College (1996). Google Scholar
12. J. Mitani and R. Uehara , Polygons folding to plural incongruent orthogonal boxes, Proc. 20th Canadian Conf. Computational Geometry (CCCG), Montréal (2008). Google Scholar
13. T. Shirakawa and R. Uehara , Common developments of three incongruent orthogonal boxes, Int. J. Comput. Geom. Appl. 23(1) (2013) 65–71. Link, Web of Science, Google Scholar
14. R. Uehara , A survey and recent results about common developments of two or more boxes, Origami6: Proc. 6th Int. Meeting on Origami in Science, Mathematics and Education (OSME 2014), Vol. 1 (American Mathematical Society, 2014), pp. 77–84. Google Scholar
15. D. Xu, T. Horiyama, T. Shirakawa and R. Uehara , Common developments of three incongruent boxes of area 30, Proc. 12th Annual Conf. Theory and Applications of Models of Computation (TAMC), eds. R. Jain, S. Jain and F. Stephan (2015), pp. 236–247. Google Scholar