Wriggling: Easy If You Are a Fat Hippo

Investigator Kevin Fisher recommends this computational geometry paper:

“Wriggling is Hard unless You Are a Fat Hippo,” Irina Kostitsyna, Valentin Polishchuk, http://arxiv.org/abs/1005.5413. The authors explain:

“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.”