%0 Journal Article
%T Simple Wriggling is Hard unless You Are a Fat Hippo
%A Irina Kostitsyna
%A Valentin Polishchuk
%J Computer Science
%D 2010
%I arXiv
%R 10.1007/978-3-642-13122-6_27
%X 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.
%U http://arxiv.org/abs/1005.5413v1