Simple Wriggling is Hard unless You Are a Fat Hippo
arXiv:1005.5413 · doi:10.1007/978-3-642-13122-6_27
Abstract
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.
A shorter version is to be presented at FUN 2010