A new algorithm for shortest paths among obstacles in the plane

We introduce a new algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles. In particular, for a given start point s, we build a planar subdivision (a shortest path map) that supports efficient queries for shortest paths from s to any destination point t. The worst-case time complexity of our algorithm is O(kn log²n), where n is the number of vertices describing the polygonal obstacles, and k is a parameter we call the "illumination depth" of the obstacle space. Our algorithm uses O(n) space, avoiding the possibly quadratic space complexity of methods that rely on visibility graphs. The quantity k is frequently significantly smaller than n, especially in some of the cases in which the visibility graph has quadratic size. In particular, k is bounded above by the number of different obstacles that touch any shortest path from s.