Paper by Erik D. Demaine
- Robert A. Hearn, Erik D. Demaine, and Greg N. Frederickson, “Hinged Dissection of Polygons is Hard”, in Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003), Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 98–102.
We show several natural questions about hinged dissections of polygons to be
PSPACE-hard. The most basic of these is: Given a hinged set of pieces and two
configurations for them, can we swing the pieces on the hinges to transform one
configuration to the other? We also consider variants in which the
configurations must be convex, the placement of hinges is not specified, or the
configurations are not supplied, but just the target shapes. We show all of
these variants to be PSPACE-hard, via a reduction from Nondeterministic
Constraint Logic .
- The paper is 4 pages.
- The paper is available in PostScript (640k), gzipped PostScript (130k), and PDF (84k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 27, 2019 by