Paper by Erik D. Demaine
- 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.
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
- 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).
- There is a revised paper with new results and a new coauthor (Greg Frederickson).
- The paper is 15 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2017 by