Paper by Erik D. Demaine
- Erik D. Demaine and Sarah Eisenstat, “Flattening Fixed-Angle Chains Is Strongly NP-Hard”, in Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), Brooklyn, New York, August 15–17, 2011, pages 314–325.
Planar configurations of fixed-angle chains and trees are well studied in
polymer science and molecular biology. We prove that it is strongly NP-hard
to decide whether a polygonal chain with fixed edge lengths and angles has a
planar configuration without crossings. In particular, flattening is NP-hard
when all the edge lengths are equal, whereas a previous (weak) NP-hardness
proof used lengths that differ in size by an exponential factor. Our
NP-hardness result also holds for (nonequilateral) chains with angles in the
range [60° − ε, 180°], whereas flattening is known
to be always possible (and hence polynomially solvable) for equilateral chains
with angles in the range (60°, 150°) and for general chains
with angles in the range [90°, 180°]. We also show that the
flattening problem is strongly NP-hard for equilateral fixed-angle trees, even
when every angle is either 90° or 180°. Finally, we show that
strong NP-hardness carries over to the previously studied problems of
computing the minimum or maximum span (distance between endpoints) among
non-crossing planar configurations.
- The paper is 12 pages.
- The paper is available in PDF (239k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 1, 2021 by