Simple wriggling is hard unless you are a fat hippo

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.