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.
In robotics thick paths were studied as routes for a circular robot. In this context, path self-overlap poses no problem as even a self-overlapping path may be traversed by the robot; that is, in contrast to VLSI, robotics research should not care about finding non-selfoverlapping paths. In @cite_2 , Chew gave an efficient algorithm for finding a shortest thick path in a polygonal domain. In a sense, our algorithm for shortest path for a short snake () may be viewed as an extension of Chew's.
@cite_2
2077163943
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.