Folding Polyominoes with Holes into a Cube

Oswin Aichholzer; Hugo A. Akitaya; Kenneth C. Cheung; Erik D. Demaine; Martin L. Demaine; Linda Kleist; Irina Kostitsyna; Maarten Löffler; Zuzana Masárová; Klara Mundilova; Christiane Schmidt; Sándor P. Fekete

Folding Polyominoes with Holes into a Cube

Oswin Aichholzer
, Hugo A. Akitaya
, Kenneth C. Cheung
, Erik D. Demaine
, Martin L. Demaine
, Linda Kleist
, Irina Kostitsyna
, Maarten Löffler
, Zuzana Masárová
, Klara Mundilova
, Christiane Schmidt
, Sándor P. Fekete

Institute of Software Engineering and Artificial Intelligence (7160)

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

Abstract

When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.

Original language	English
Title of host publication	Proc. 31th Annual Canadian Conference on Computational Geometry CCCG 2019
Place of Publication	Edmonton, Alberta, Canada
Pages	164-170
Number of pages	7
Publication status	Published - 2019

Fields of Expertise

Information, Communication & Computing

Access to Document

https://sites.ualberta.ca/~cccg2019/cccg2019_proceedings.pdf

Cite this

Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Kleist, L., Kostitsyna, I., Löffler, M., Masárová, Z., Mundilova, K., Schmidt, C., & Fekete, S. P. (2019). Folding Polyominoes with Holes into a Cube. In Proc. 31th Annual Canadian Conference on Computational Geometry CCCG 2019 (pp. 164-170). https://sites.ualberta.ca/~cccg2019/cccg2019_proceedings.pdf

Aichholzer, O, Akitaya, HA, Cheung, KC, Demaine, ED, Demaine, ML, Kleist, L, Kostitsyna, I, Löffler, M, Masárová, Z, Mundilova, K, Schmidt, C & Fekete, SP 2019, Folding Polyominoes with Holes into a Cube. in Proc. 31th Annual Canadian Conference on Computational Geometry CCCG 2019. Edmonton, Alberta, Canada, pp. 164-170. <https://sites.ualberta.ca/~cccg2019/cccg2019_proceedings.pdf>

@inproceedings{e70781686b4d4749a414cdaadd1f5b50,

title = "Folding Polyominoes with Holes into a Cube",

abstract = "When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.",

author = "Oswin Aichholzer and Akitaya, \{Hugo A.\} and Cheung, \{Kenneth C.\} and Demaine, \{Erik D.\} and Demaine, \{Martin L.\} and Linda Kleist and Irina Kostitsyna and Maarten L{\"o}ffler and Zuzana Mas{\'a}rov{\'a} and Klara Mundilova and Christiane Schmidt and Fekete, \{S{\'a}ndor P.\}",

year = "2019",

language = "English",

pages = "164--170",

booktitle = "Proc. 31th Annual Canadian Conference on Computational Geometry CCCG 2019",

}

TY - GEN

T1 - Folding Polyominoes with Holes into a Cube

AU - Aichholzer, Oswin

AU - Akitaya, Hugo A.

AU - Cheung, Kenneth C.

AU - Demaine, Erik D.

AU - Demaine, Martin L.

AU - Kleist, Linda

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Masárová, Zuzana

AU - Mundilova, Klara

AU - Schmidt, Christiane

AU - Fekete, Sándor P.

PY - 2019

Y1 - 2019

N2 - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.

AB - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.

M3 - Conference paper

SP - 164

EP - 170

BT - Proc. 31th Annual Canadian Conference on Computational Geometry CCCG 2019

CY - Edmonton, Alberta, Canada

ER -