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 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.

Updates:

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”.

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)