Paper by Erik D. Demaine

Reference:

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.

Abstract:

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 [4].

Length:

The paper is 4 pages.

Availability:

The paper is available in PostScript (640k), gzipped PostScript (130k), and PDF (84k).

See information on file formats.

[Google Scholar search]