Paper by Erik D. Demaine
- Erik D. Demaine, Martin L. Demaine, David Eppstein, Greg N. Frederickson, and Erich Friedman, “Hinged Dissection of Polyominoes and Polyforms”, Computational Geometry: Theory and Applications, volume 31, number 3, June 2005, pages 237–262. Special issue of selected papers from the 11th Canadian Conference on Computational Geometry, 1999.
A hinged dissection of a set of polygons S is a collection of polygonal
pieces hinged together at vertices that can be folded into any member of
S. We present a hinged dissection of all edge-to-edge gluings of
n congruent copies of a polygon P that join corresponding edges
of P. This construction uses k n pieces, where
k is the number of vertices of P. When P is a regular
polygon, we show how to reduce the number of pieces to
⌈k / 2⌉ (n − 1). In
particular, we consider polyominoes (made up of unit squares), polyiamonds
(made up of equilateral triangles), and polyhexes (made up of regular
hexagons). We also give a hinged dissection of all polyabolos (made up of
right isosceles triangles), which do not fall under the general result
mentioned above. Finally, we show that if P can be hinged into
Q, then any edge-to-edge gluing of n congruent copies of P
can be hinged into any edge-to-edge gluing of n congruent copies of
- This paper is also available as arXiv:cs.CG/9907018 of the Computing Research Repository (CoRR). The paper is also available from ScienceDirect.
- The paper is 27 pages.
- The paper is available in PostScript (671k), gzipped PostScript (210k), and PDF (238k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- CCCG99a (Hinged Dissection of Polyominoes and Polyiamonds)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 27, 2017 by