Paper by Erik D. Demaine

Reference:

Greg Aloupis, Prosenjit K. Bose, Sebastien Collette, Erik D. Demaine, Martin L. Demaine, Karim Douieb, Vida Dujmović, John Iacono, Stefan Langerman, and Pat Morin, “Common Unfoldings of Polyominoes and Polycubes”, in Revised Papers from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Lecture Notes in Computer Science, volume 7033, Dalian, China, November 3–6, 2010, pages 44–54.

BibTeX

@InProceedings{Cubigami_CGGA2010full,
  AUTHOR        = {Greg Aloupis and Prosenjit K. Bose and Sebastien Collette
                   and Erik D. Demaine and Martin L. Demaine and Karim Douieb
                   and Vida Dujmovi\'c and John Iacono and Stefan Langerman and
                   Pat Morin},
  TITLE         = {Common Unfoldings of Polyominoes and Polycubes},
  BOOKTITLE     = {Revised Papers from the China-Japan Joint Conference on
                   Computational Geometry, Graphs and Applications (CGGA 2010)},
  bookurl       = {http://www.dlmu.edu.cn/cgga2010/},
  VOLUME        = 7033,
  SERIES        = {Lecture Notes in Computer Science},
  ADDRESS       = {Dalian, China},
  MONTH         = {November 3--6},
  YEAR          = 2010,
  PAGES         = {44--54},

  length        = {11 pages},
  withstudent   = 1,
  replaces      = {Cubigami_CGGA2010},
  papers        = {Cubigami_CGGA2010},
  updates       = {
    <ul>
    <li> In the abstract, the phrase &ldquo;we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding&rdquo; should be replaced with &ldquo;we show here that all <b>27</b> tree-like pentacubes have no such common unfolding, although <b>23</b> of them have a common unfolding&rdquo;.
    <li> Section 3.3 says &ldquo;There are several two-sided common unfoldings for a set of 23 pentacubes (one is pictured below)&rdquo; but one is not actually pictured. (It was in the <a href="../Cubigami_CGGA2010/">short paper</a>.) Here is one: <br> <a href="23shapes.pdf"><img style="max-width: 100%" src="23shapes.png"></a>
    <li> In Section 3.3, the phrase &ldquo;There is a unique two-sided unfolding of all 22 non-planar pentacubes (Figure 8(12-27))&rdquo; should be replaced with &ldquo;There is a unique two-sided unfolding of all <b>16</b> non-planar pentacubes (Figure 8(12-27)), which also folds into 6 planar pentacubes for a total of 22 pentacubes&rdquo;.
    </ul>
  },
  doi           = {https://dx.doi.org/10.1007/978-3-642-24983-9_5},
  dblp          = {https://dblp.org/rec/conf/cgga/AloupisBCDDDDILM10},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-642-24983-9_5">SpringerLink</A>.},
}

Abstract:

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 27 tree-like pentacubes have no such common unfolding, although 23 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.

Comments:

This paper is also available from SpringerLink.

Updates:

• In the abstract, the phrase “we show here that all 23 tree-like pentacubes have no such common unfolding, although 22 of them have a common unfolding” should be replaced with “we show here that all 27 tree-like pentacubes have no such common unfolding, although 23 of them have a common unfolding”.
• Section 3.3 says “There are several two-sided common unfoldings for a set of 23 pentacubes (one is pictured below)” but one is not actually pictured. (It was in the short paper.) Here is one:
  
• In Section 3.3, the phrase “There is a unique two-sided unfolding of all 22 non-planar pentacubes (Figure 8(12-27))” should be replaced with “There is a unique two-sided unfolding of all 16 non-planar pentacubes (Figure 8(12-27)), which also folds into 6 planar pentacubes for a total of 22 pentacubes”.

Length:

The paper is 11 pages.

Availability:

The paper is available in PDF (2750k).

See information on file formats.

[Google Scholar search]

Related papers:

Cubigami_CGGA2010 (Common Unfoldings of Polyominoes and Polycubes)