Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{FixedAngle_WADS2011,
  AUTHOR        = {Erik D. Demaine and Sarah Eisenstat},
  TITLE         = {Flattening Fixed-Angle Chains Is Strongly {NP}-Hard},
  BOOKTITLE     = {Proceedings of the 12th Algorithms and Data Structures
                   Symposium (WADS 2011)},
  bookurl       = {http://www.wads.org/},
  ADDRESS       = {Brooklyn, New York},
  MONTH         = {August 15--17},
  YEAR          = 2011,
  PAGES         = {314--325},

  length        = {12 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-642-22300-6_27},
  dblp          = {https://dblp.org/rec/conf/wads/DemaineE11},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-642-22300-6_27">SpringerLink</A>.},
}

Abstract:

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.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 12 pages.

Availability:

The paper is available in PDF (239k).

See information on file formats.

[Google Scholar search]