Folding polyominoes with holes into a cube

O. Aichholzer, H.A. Akitaya, K.C. Cheung, E.D. Demaine, M.L. Demaine, S.P. Fekete, L. Kleist, I. Kostitsyna, M. Löffler, Z. Masárová, K. Mundilova, C. Schmidt, Computational Geometry: Theory and Applications 93 (n.d.).


Journal Article | In Press | English

Scopus indexed
Author
Aichholzer, Oswin; Akitaya, Hugo A.; Cheung, Kenneth C.; Demaine, Erik D.; Demaine, Martin L.; Fekete, Sándor P.; Kleist, Linda; Kostitsyna, Irina; Löffler, Maarten; Masárová, ZuzanaIST Austria ; Mundilova, Klara; Schmidt, Christiane
All
Department
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 one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special “basic” holes guarantee foldability.
Publishing Year
Date Published
2020-08-31
Journal Title
Computational Geometry: Theory and Applications
Acknowledgement
This research was performed in part at the 33rd Bellairs Winter Workshop on Computational Geometry. We thank all other participants for a fruitful atmosphere. H. Akitaya was supported by NSF CCF-1422311 & 1423615. Z. Masárová was partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.
Volume
93
Article Number
101700
ISSN
IST-REx-ID

Cite this

Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 93. doi:10.1016/j.comgeo.2020.101700
Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M. L., Fekete, S. P., … Schmidt, C. (n.d.). Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications, 93. https://doi.org/10.1016/j.comgeo.2020.101700
Aichholzer, Oswin, Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Linda Kleist, et al. “Folding Polyominoes with Holes into a Cube.” Computational Geometry: Theory and Applications 93 (n.d.). https://doi.org/10.1016/j.comgeo.2020.101700.
O. Aichholzer et al., “Folding polyominoes with holes into a cube,” Computational Geometry: Theory and Applications, vol. 93.
Aichholzer O, Akitaya HA, Cheung KC, Demaine ED, Demaine ML, Fekete SP, Kleist L, Kostitsyna I, Löffler M, Masárová Z, Mundilova K, Schmidt C. Folding polyominoes with holes into a cube. Computational Geometry: Theory and Applications. 93.
Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Computational Geometry: Theory and Applications, vol. 93, 101700, Elsevier, doi:10.1016/j.comgeo.2020.101700.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Shorter Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1910.09917v3

Search this title in

Google Scholar