Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, David Eppstein, and Erich Friedman, “Hinged Dissection of Polyominoes and Polyforms”, in Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG'99), Vancouver, British Columbia, Canada, August 15–18, 1999.

BibTeX

@InProceedings{CCCG99a,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and David Eppstein and
                   Erich Friedman},
  TITLE         = {Hinged Dissection of Polyominoes and Polyforms},
  BOOKTITLE     = {Proceedings of the 11th Canadian Conference on Computational
                   Geometry (CCCG'99)},
  BOOKURL       = {http://www.cs.ubc.ca/conferences/CCCG/},
  MONTH         = {August 15--18},
  YEAR          = 1999,
  ADDRESS       = {Vancouver, British Columbia, Canada},

  award         = {Invited to special issue of \emph{Computational Geometry: Theory and Applications}.},
  length        = {15 pages},
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineDEF99},
  ee            = {http://www.cccg.ca/proceedings/1999/fp37.pdf},
  comments      = {This paper is also available from the
                   <A HREF="http://www.cs.ubc.ca/conferences/CCCG/elec_proc/elecproc.html">
                   electronic proceedings</A> as
                   <A HREF="http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp37.ps.gz">http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp37.ps.gz</A>.
                   It is also available as
                   <A HREF="http://arXiv.org/abs/cs.CG/9907018v1">
                   arXiv:cs.CG/9907018v1</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.},
  updates       = {There is a
                   <A HREF="../HingedPolyforms/">revised paper</A>
                   with new results and a new coauthor (Greg Frederickson).},
  papers        = {HingedPolyforms},
  unrefereed    = 1,
}

Abstract:

This paper shows how to hinge together a collection of polygons at vertices in such a way that a single object can be reshaped into any n-omino, for a given value of n. An n-omino is defined generally as a connected union of n unit squares on the integer grid. Our best dissection uses 2 (n − 1) polygons. We generalize this result to the connected unions of nonoverlapping equal-size regular k-gons joined edge-to-edge, which includes n-iamonds (k = 3) and n-hexes (k = 6). Our best dissection uses ⌈k / 2⌉ (n − 1) polygons. We also explore polyabolos, that is, connected unions of nonoverlapping equal-size isosceles right triangles joined edge-to-edge, and give a hinged dissection using 4 n polygons. Finally, we generalize our result about regular polygons to connected unions of nonoverlapping copies of any polygon P, all with the same orientation, that join corresponding edges of P. This solution uses k n pieces where k is the number of vertices of P.

Comments:

This paper is also available from the electronic proceedings as http://www.cs.ubc.ca/conferences/CCCG/elec_proc/fp37.ps.gz. It is also available as arXiv:cs.CG/9907018v1 of the Computing Research Repository (CoRR).

Updates:

There is a revised paper with new results and a new coauthor (Greg Frederickson).

Length:

The paper is 15 pages.

Availability:

The paper is available in PostScript (709k) and gzipped PostScript (198k).

See information on file formats.

[Google Scholar search]

Related papers:

HingedPolyforms (Hinged Dissection of Polyominoes and Polyforms)