Planning the shortest path for a disc in <i>O</i>(<i>n</i>²log <i>n</i>) 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(n2log 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.