We prove that it is NP-hard to decide whether two points in a polygonal domain with holes can be connected by a wire. This implies that finding any approximation to the shortest path for a long snake amidst polygonal obstacles is NP-hard. On the positive side, we show that snake’s problem is ”length-tractable”: if the snake is ”fat”, i.e., its length/width ratio is small, the shortest path can be computed in polynomial time.
|Title of host publication||Fun with algorithms|
|Subtitle of host publication||5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings|
|Editors||P. Boldi, L. Gargano|
|Place of Publication||Berlin|
|Number of pages||12|
|Publication status||Published - 2010|
|Name||Lecture Notes in Computer Science (LNCS)|