Paper by Erik D. Demaine

Reference:

Oswin Aichholzer, Michael Biro, Erik D. Demaine, Martin L. Demaine, David Eppstein, Sándor P. Fekete, Adam Hesterberg, Irina Kostitsyna, and Christiane Schmidt, “Folding Polyominoes into (Poly)Cubes”, International Journal of Computational Geometry and Applications, volume 28, number 3, 2018, pages 197–226.

Abstract:

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 180°), 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.

Comments:

This paper is also available as arXiv:1712.09317 and from World Scientific.

Length:

The paper is 30 pages.

Availability:

The paper is available in PDF (761k).

See information on file formats.

[Google Scholar search]

Related papers:

PolyformFolding_CCCG2015 (Folding Polyominoes into (Poly)Cubes)

CubeFolding_CCCG2020 (Folding Small Polyominoes into a Unit Cube)

CubeFoldingHoles_CGTA (Folding Polyominoes with Holes into a Cube)