Paper by Erik D. Demaine

Reference:

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), College Park, Maryland, June 9–11, 2008, pages 110–119.

BibTeX

@InProceedings{HingedDissections_SoCG2008,
  AUTHOR        = {Timothy G. Abbott and Zachary Abel and David Charlton and
                   Erik D. Demaine and Martin L. Demaine and Scott D. Kominers},
  TITLE         = {Hinged Dissections Exist},
  BOOKTITLE     = {Proceedings of the 24th Annual ACM Symposium on
                   Computational Geometry (SoCG 2008)},
  bookurl       = {http://www.umiacs.umd.edu/conferences/socg2008/},
  ADDRESS       = {College Park, Maryland},
  MONTH         = {June 9--11},
  YEAR          = 2008,
  PAGES         = {110--119},

  withstudent   = 1,
  papers        = {HingedDissections_DCG},
  doi           = {https://dx.doi.org/10.1145/1377676.1377695},
  dblp          = {https://dblp.org/rec/conf/compgeom/AbbottACDDK08},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/0712.2094">arXiv:0712.2094</A>, and from <A HREF="https://doi.org/10.1145/1377676.1377695">ACM</A>.},
}

Abstract:

We prove that any finite collection of polygons of equal area has a common hinged dissection, that is, a chain of polygons hinged at vertices that can be folded in the plane continuously without self-intersection to form any polygon in the collection. This result settles the open problem about the existence of hinged dissections between pairs of polygons that goes back implicitly to 1864 and has been studied extensively in the past ten years. Our result generalizes and indeed builds upon the result from 1814 that polygons have common dissections (without hinges). We also extend our result to edge-hinged dissections of solid 3D polyhedra that have a common (unhinged) dissection, as determined by Dehn's 1900 solution to Hilbert's Third Problem. Our proofs are constructive, giving explicit algorithms in all cases. For a constant number of planar polygons, both the number of pieces and running time required by our construction are pseudopolynomial. This bound is the best possible even for unhinged dissections. Hinged dissections have possible applications to reconfigurable robotics, programmable matter, and nanomanufacturing.

Comments:

This paper is also available as arXiv:0712.2094, and from ACM.

Availability:

The paper is available in PostScript (1931k), gzipped PostScript (719k), and PDF (580k).

See information on file formats.

[Google Scholar search]

Related papers:

HingedDissections_DCG (Hinged Dissections Exist)