next up previous
Next: Problem 48: Bounded-Degree Minimum Up: The Open Problems Project Previous: Problem 46: 3D Minimum-Bend


Problem 47: Hinged Dissections

Statement
Does every pair of equal-area polygons have a hinged dissection? A dissection of one polygon A to another B is a partition of A into a finite number of pieces that may be reassembled to form B. A hinged dissection is a dissection where the pieces are hinged at vertices and the reassembling is achieved by rotating the pieces about their hinges in the plane of the polygons.
Origin
[DDE+03], [Fre02, p. 3].
Status/Conjectures
Now settled: Hinged dissections exist [AAC+08]. Update to this entry soon.
Partial and Related Results
There are two main partial results. First, any two polyominoes of the same area have a hinged dissection [DDE+03]. A polyomino is a polygon formed by joining unit squares at their edges; see [Kla97] and Problem 37. The polyomino result generalizes to hinged dissections of all edge-to-corresponding-edge gluings of congruent copies of any polygon. Second, any asymmetric polygon has a hinged dissection to its mirror image [Epp01]. Both of these results interpret the problem as ignoring possible intersections between the pieces as they hinge, following what Frederickson calls the ``wobbly-hinged'' model. This freedom may not be necessary, although this seems not to be established in the literature.

Many specific examples of hinged dissections can be found in [Fre02].

Appearances
[O'R02b].
Categories
polygons
Entry Revision History
J. O'Rourke, 25 Mar 2003; J. O'Rourke, 23 Jan 2009.

Bibliography

AAC+08
Timothy G. Abbott, Zachary Abel, David Charlton, Erik D. Demaine, Martin L. Demaine, and Scott D. Kominers.
Hinged dissections exist.
In Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), pages 110-119, College Park, Maryland, June 9-11 2008.

DDE+03
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, 2003.
To appear. arXiv:cs.CG/9907018, http://www.arXiv.org/abs/cs.CG/9907018. Revised version of paper in Proc. 11th Canad. Conf. Comput. Geom. 1999, 15-18.

Epp01
David Eppstein.
Hinged kite mirror dissection.
ACM Computing Research Repository, June 2001.
arXiv:cs.CG/0106032, http://www.arXiv.org/abs/cs.CG/0106032.

Fre02
Greg Frederickson.
Hinged Dissections: Swinging & Twisting.
Cambridge University Press, 2002.

Kla97
David A. Klarner.
Polyominoes.
In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 12, pages 225-242. CRC Press LLC, Boca Raton, FL, 1997.

O'R02b
Joseph O'Rourke.
Computational geometry column 44.
Internat. J. Comput. Geom. Appl., 13(3):273-275, 2002.
Also in SIGACT News, 34(2):58-60 (2002), Issue 127.


next up previous
Next: Problem 48: Bounded-Degree Minimum Up: The Open Problems Project Previous: Problem 46: 3D Minimum-Bend
The Open Problems Project - December 04, 2015