Folding Polyominoes into (Poly)Cubes
© 2018 World Scientific Publishing Company. 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 (...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
World Scientific Pub Co Pte Lt
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135863 |
| _version_ | 1811088769584988160 |
|---|---|
| author | Aichholzer, Oswin Biro, Michael Demaine, Erik D Demaine, Martin L Eppstein, David Fekete, Sándor P Hesterberg, Adam Kostitsyna, Irina Schmidt, Christiane |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aichholzer, Oswin Biro, Michael Demaine, Erik D Demaine, Martin L Eppstein, David Fekete, Sándor P Hesterberg, Adam Kostitsyna, Irina Schmidt, Christiane |
| author_sort | Aichholzer, Oswin |
| collection | MIT |
| description | © 2018 World Scientific Publishing Company. 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. |
| first_indexed | 2024-09-23T14:07:15Z |
| format | Article |
| id | mit-1721.1/135863 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T14:07:15Z |
| publishDate | 2021 |
| publisher | World Scientific Pub Co Pte Lt |
| record_format | dspace |
| spelling | mit-1721.1/1358632023-09-13T17:58:17Z Folding Polyominoes into (Poly)Cubes Aichholzer, Oswin Biro, Michael Demaine, Erik D Demaine, Martin L Eppstein, David Fekete, Sándor P Hesterberg, Adam Kostitsyna, Irina Schmidt, Christiane Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Mathematics © 2018 World Scientific Publishing Company. 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. 2021-10-27T20:29:41Z 2021-10-27T20:29:41Z 2018 2019-06-11T12:17:35Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135863 en 10.1142/S0218195918500048 International Journal of Computational Geometry and Applications Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf World Scientific Pub Co Pte Lt arXiv |
| spellingShingle | Aichholzer, Oswin Biro, Michael Demaine, Erik D Demaine, Martin L Eppstein, David Fekete, Sándor P Hesterberg, Adam Kostitsyna, Irina Schmidt, Christiane Folding Polyominoes into (Poly)Cubes |
| title | Folding Polyominoes into (Poly)Cubes |
| title_full | Folding Polyominoes into (Poly)Cubes |
| title_fullStr | Folding Polyominoes into (Poly)Cubes |
| title_full_unstemmed | Folding Polyominoes into (Poly)Cubes |
| title_short | Folding Polyominoes into (Poly)Cubes |
| title_sort | folding polyominoes into poly cubes |
| url | https://hdl.handle.net/1721.1/135863 |
| work_keys_str_mv | AT aichholzeroswin foldingpolyominoesintopolycubes AT biromichael foldingpolyominoesintopolycubes AT demaineerikd foldingpolyominoesintopolycubes AT demainemartinl foldingpolyominoesintopolycubes AT eppsteindavid foldingpolyominoesintopolycubes AT feketesandorp foldingpolyominoesintopolycubes AT hesterbergadam foldingpolyominoesintopolycubes AT kostitsynairina foldingpolyominoesintopolycubes AT schmidtchristiane foldingpolyominoesintopolycubes |