Paper by Martin L. Demaine

Reference:

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

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/9970183v1 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)