Simple Wriggling is Hard unless You Are a Fat Hippo

Irina Kostitsyna, Valentin Polishchuk

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 pa…