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.

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.

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)