Next: Problem 48: Bounded-Degree Minimum Euclidean Spanning Tree
Previous: Problem 46: 3D Minimum-Bend Orthogonal Graph Drawings
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.
Now settled: Hinged dissections exist [AAC+08]. Update to this entry soon.
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].
polygons
J. O’Rourke, 25 Mar 2003; J. O’Rourke, 23 Jan 2009.
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.
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, 31(3):237–262, 2003. arXiv:cs.CG/9907018.
David Eppstein. Hinged kite mirror dissection. ACM Computing Research Repository, June 2001. arXiv:cs.CG/0106032, http://www.arXiv.org/abs/cs.CG/0106032.
Greg Frederickson. Hinged Dissections: Swinging & Twisting. Cambridge University Press, 2002.
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.
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.