Common unfoldings of polyominoes and polycubes
Computational Geometry, Graphs and Applications 9th International Conference, CGGA 2010, Dalian, China, November 3-6, 2010, Revised Selected Papers
Main Authors: | , , , , , , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | en_US |
Published: |
Springer Berlin / Heidelberg
2012
|
Online Access: | http://hdl.handle.net/1721.1/73836 https://orcid.org/0000-0003-3803-5703 |
_version_ | 1826194969644236800 |
---|---|
author | Aloupis, Greg Bose, Prosenjit Collette, Sebastien Demaine, Erik D. Demaine, Martin L. Douieb, Karim Dujmovic, Vida Iacono, John Langerman, Stefan Morin, Pat |
author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Aloupis, Greg Bose, Prosenjit Collette, Sebastien Demaine, Erik D. Demaine, Martin L. Douieb, Karim Dujmovic, Vida Iacono, John Langerman, Stefan Morin, Pat |
author_sort | Aloupis, Greg |
collection | MIT |
description | Computational Geometry, Graphs and Applications 9th International Conference, CGGA 2010, Dalian, China, November 3-6, 2010, Revised Selected Papers |
first_indexed | 2024-09-23T10:04:41Z |
format | Article |
id | mit-1721.1/73836 |
institution | Massachusetts Institute of Technology |
language | en_US |
last_indexed | 2024-09-23T10:04:41Z |
publishDate | 2012 |
publisher | Springer Berlin / Heidelberg |
record_format | dspace |
spelling | mit-1721.1/738362022-09-26T15:34:57Z Common unfoldings of polyominoes and polycubes Aloupis, Greg Bose, Prosenjit Collette, Sebastien Demaine, Erik D. Demaine, Martin L. Douieb, Karim Dujmovic, Vida Iacono, John Langerman, Stefan Morin, Pat Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Demaine, Martin L. Computational Geometry, Graphs and Applications 9th International Conference, CGGA 2010, Dalian, China, November 3-6, 2010, Revised Selected Papers This paper studies common unfoldings of various classes of polycubes, as well as a new type of unfolding of polyominoes. Previously, Knuth and Miller found a common unfolding of all tree-like tetracubes. By contrast, we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding. On the positive side, we show that there is an unfolding common to all “non-spiraling” k-ominoes, a result that extends to planar non-spiraling k-cubes. 2012-10-10T16:01:44Z 2012-10-10T16:01:44Z 2011-11 2010-11 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-24982-2 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73836 Aloupis, Greg et al. “Common Unfoldings of Polyominoes and Polycubes.” Computational Geometry, Graphs and Applications. Ed. Jin Akiyama et al. LNCS Vol. 7033. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 44–54. https://orcid.org/0000-0003-3803-5703 en_US http://dx.doi.org/10.1007/978-3-642-24983-9_5 Computational Geometry, Graphs and Applications Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
spellingShingle | Aloupis, Greg Bose, Prosenjit Collette, Sebastien Demaine, Erik D. Demaine, Martin L. Douieb, Karim Dujmovic, Vida Iacono, John Langerman, Stefan Morin, Pat Common unfoldings of polyominoes and polycubes |
title | Common unfoldings of polyominoes and polycubes |
title_full | Common unfoldings of polyominoes and polycubes |
title_fullStr | Common unfoldings of polyominoes and polycubes |
title_full_unstemmed | Common unfoldings of polyominoes and polycubes |
title_short | Common unfoldings of polyominoes and polycubes |
title_sort | common unfoldings of polyominoes and polycubes |
url | http://hdl.handle.net/1721.1/73836 https://orcid.org/0000-0003-3803-5703 |
work_keys_str_mv | AT aloupisgreg commonunfoldingsofpolyominoesandpolycubes AT boseprosenjit commonunfoldingsofpolyominoesandpolycubes AT collettesebastien commonunfoldingsofpolyominoesandpolycubes AT demaineerikd commonunfoldingsofpolyominoesandpolycubes AT demainemartinl commonunfoldingsofpolyominoesandpolycubes AT douiebkarim commonunfoldingsofpolyominoesandpolycubes AT dujmovicvida commonunfoldingsofpolyominoesandpolycubes AT iaconojohn commonunfoldingsofpolyominoesandpolycubes AT langermanstefan commonunfoldingsofpolyominoesandpolycubes AT morinpat commonunfoldingsofpolyominoesandpolycubes |