Name
Abstract | ||
|---|---|---|
We show several natural questions about hinged dissec- tions of polygons to be PSPACE-hard. The most basic of these is: Given a hinged set of pieces and two con- figurations 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). |
Year | Venue | Field |
|---|---|---|
2003 | CCCG | Discrete mathematics,Combinatorics,Polygon,Nondeterministic algorithm,Computer science,Regular polygon,Hinge,Swing |
DocType | Citations | PageRank |
Conference | 1 | 0.37 |
References | Authors | |
2 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert A. Hearn | 1 | 169 | 20.52 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Greg N. Frederickson | 3 | 2176 | 307.42 |