---
_id: '8317'
abstract:
- lang: eng
text: 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.
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.
article_number: '101700'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- first_name: Hugo A.
full_name: Akitaya, Hugo A.
last_name: Akitaya
- first_name: Kenneth C.
full_name: Cheung, Kenneth C.
last_name: Cheung
- first_name: Erik D.
full_name: Demaine, Erik D.
last_name: Demaine
- first_name: Martin L.
full_name: Demaine, Martin L.
last_name: Demaine
- first_name: Sándor P.
full_name: Fekete, Sándor P.
last_name: Fekete
- first_name: Linda
full_name: Kleist, Linda
last_name: Kleist
- first_name: Irina
full_name: Kostitsyna, Irina
last_name: Kostitsyna
- first_name: Maarten
full_name: Löffler, Maarten
last_name: Löffler
- first_name: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Klara
full_name: Mundilova, Klara
last_name: Mundilova
- first_name: Christiane
full_name: Schmidt, Christiane
last_name: Schmidt
citation:
ama: 'Aichholzer O, Akitaya HA, Cheung KC, et al. Folding polyominoes with holes
into a cube. Computational Geometry: Theory and Applications. 2021;93.
doi:10.1016/j.comgeo.2020.101700'
apa: 'Aichholzer, O., Akitaya, H. A., Cheung, K. C., Demaine, E. D., Demaine, M.
L., Fekete, S. P., … Schmidt, C. (2021). Folding polyominoes with holes into a
cube. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2020.101700'
chicago: '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.
Elsevier, 2021. https://doi.org/10.1016/j.comgeo.2020.101700.'
ieee: 'O. Aichholzer et al., “Folding polyominoes with holes into a cube,”
Computational Geometry: Theory and Applications, vol. 93. Elsevier, 2021.'
ista: '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. 2021. Folding
polyominoes with holes into a cube. Computational Geometry: Theory and Applications.
93, 101700.'
mla: 'Aichholzer, Oswin, et al. “Folding Polyominoes with Holes into a Cube.” Computational
Geometry: Theory and Applications, vol. 93, 101700, Elsevier, 2021, doi:10.1016/j.comgeo.2020.101700.'
short: '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 (2021).'
corr_author: '1'
date_created: 2020-08-30T22:01:09Z
date_published: 2021-02-01T00:00:00Z
date_updated: 2026-06-18T19:14:36Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.comgeo.2020.101700
external_id:
arxiv:
- '1910.09917'
isi:
- '000579185100004'
intvolume: ' 93'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1910.09917v3
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
eissn:
- 1879-081X
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
record:
- id: '6989'
relation: shorter_version
status: public
scopus_import: '1'
status: public
title: Folding polyominoes with holes into a cube
type: journal_article
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 93
year: '2021'
...
---
OA_type: free access
_id: '3971'
abstract:
- lang: eng
text: The Reeb graph is a useful tool in visualizing real-valued data obtained from
computational simulations of physical processes. We characterize the evolution
of the Reeb graph of a time-varying continuous function defined in three-dimensional
space. We show how to maintain the Reeb graph over time and compress the entire
sequence of Reeb graphs into a single, partially persistent data structure, and
augment this data structure with Betti numbers to describe the topology of level
sets and with path seeds to assist in the fast extraction of level sets for visualization.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: John
full_name: Harer, John
last_name: Harer
- first_name: Ajith
full_name: Mascarenhas, Ajith
last_name: Mascarenhas
- first_name: Valerio
full_name: Pascucci, Valerio
last_name: Pascucci
- first_name: Jack
full_name: Snoeyink, Jack
last_name: Snoeyink
citation:
ama: 'Edelsbrunner H, Harer J, Mascarenhas A, Pascucci V, Snoeyink J. Time-varying
Reeb graphs for continuous space-time data. Computational Geometry: Theory
and Applications. 2008;41(3):149-166. doi:10.1016/j.comgeo.2007.11.001'
apa: 'Edelsbrunner, H., Harer, J., Mascarenhas, A., Pascucci, V., & Snoeyink,
J. (2008). Time-varying Reeb graphs for continuous space-time data. Computational
Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2007.11.001'
chicago: 'Edelsbrunner, Herbert, John Harer, Ajith Mascarenhas, Valerio Pascucci,
and Jack Snoeyink. “Time-Varying Reeb Graphs for Continuous Space-Time Data.”
Computational Geometry: Theory and Applications. Elsevier, 2008. https://doi.org/10.1016/j.comgeo.2007.11.001.'
ieee: 'H. Edelsbrunner, J. Harer, A. Mascarenhas, V. Pascucci, and J. Snoeyink,
“Time-varying Reeb graphs for continuous space-time data,” Computational Geometry:
Theory and Applications, vol. 41, no. 3. Elsevier, pp. 149–166, 2008.'
ista: 'Edelsbrunner H, Harer J, Mascarenhas A, Pascucci V, Snoeyink J. 2008. Time-varying
Reeb graphs for continuous space-time data. Computational Geometry: Theory and
Applications. 41(3), 149–166.'
mla: 'Edelsbrunner, Herbert, et al. “Time-Varying Reeb Graphs for Continuous Space-Time
Data.” Computational Geometry: Theory and Applications, vol. 41, no. 3,
Elsevier, 2008, pp. 149–66, doi:10.1016/j.comgeo.2007.11.001.'
short: 'H. Edelsbrunner, J. Harer, A. Mascarenhas, V. Pascucci, J. Snoeyink, Computational
Geometry: Theory and Applications 41 (2008) 149–166.'
date_created: 2018-12-11T12:06:12Z
date_published: 2008-11-01T00:00:00Z
date_updated: 2026-05-29T09:15:13Z
day: '01'
doi: 10.1016/j.comgeo.2007.11.001
extern: '1'
intvolume: ' 41'
issue: '3'
language:
- iso: eng
month: '11'
oa_version: None
page: 149 - 166
publication: 'Computational Geometry: Theory and Applications'
publication_identifier:
eissn:
- 1879-081X
issn:
- 0925-7721
publication_status: published
publisher: Elsevier
publist_id: '2158'
status: public
title: Time-varying Reeb graphs for continuous space-time data
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 41
year: '2008'
...