Flattening fixed-angle chains is strongly NP-hard
12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin / Heidelberg
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73923 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| _version_ | 1826197873966972928 |
|---|---|
| author | Demaine, Erik D. Eisenstat, Sarah Charmian |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Eisenstat, Sarah Charmian |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings |
| first_indexed | 2024-09-23T10:54:49Z |
| format | Article |
| id | mit-1721.1/73923 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:54:49Z |
| publishDate | 2012 |
| publisher | Springer Berlin / Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/739232022-09-30T23:51:50Z Flattening fixed-angle chains is strongly NP-hard Demaine, Erik D. Eisenstat, Sarah Charmian Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Eisenstat, Sarah Charmian 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings 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. 2012-10-12T14:57:06Z 2012-10-12T14:57:06Z 2011-08 2011-08 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-22299-3 0302-9743 1611-3349 http://hdl.handle.net/1721.1/73923 Demaine, Erik D., and Sarah Eisenstat. “Flattening Fixed-Angle Chains Is Strongly NP-Hard.” Algorithms and Data Structures. Ed. Frank Dehne, John Iacono, & Jörg-Rüdiger Sack. LNCS Vol. 6844. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. 314–325. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 en_US http://dx.doi.org/10.1007/978-3-642-22300-6_27 Algorithms and Data Structures Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer Berlin / Heidelberg MIT web domain |
| spellingShingle | Demaine, Erik D. Eisenstat, Sarah Charmian Flattening fixed-angle chains is strongly NP-hard |
| title | Flattening fixed-angle chains is strongly NP-hard |
| title_full | Flattening fixed-angle chains is strongly NP-hard |
| title_fullStr | Flattening fixed-angle chains is strongly NP-hard |
| title_full_unstemmed | Flattening fixed-angle chains is strongly NP-hard |
| title_short | Flattening fixed-angle chains is strongly NP-hard |
| title_sort | flattening fixed angle chains is strongly np hard |
| url | http://hdl.handle.net/1721.1/73923 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3182-1675 |
| work_keys_str_mv | AT demaineerikd flatteningfixedanglechainsisstronglynphard AT eisenstatsarahcharmian flatteningfixedanglechainsisstronglynphard |