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.
Given a robot R, a set S of obstacles, and points p and q, the Shortest Path Problem is to find the shortest path for R to move from p to q without crashing into any of the obstacles. We show that if the problem is restricted to a disc-shaped robot in the plane with nonintersecting polygons as obstacles then the shortest path can be found in time O(n 2 log n) where n is the number of edges that make up the polygonal obstacles. This matches the best time currently known for the simpler problem of finding the shortest path in the plane for a point robot.