Shortest Paths in the Plane with Obstacle Violations
John E. Hershberger, Neeraj Kumar, Subhash Suri · Algorithmica · 2020
We study the problem of finding shortest paths in the plane among h convex obstacles, where the path is allowed to pass through (violate) up to k obstacles, for $$k \le h$$ . Equivalently, the problem is to find shortest paths that become obstacle-free if k obstacles are removed from the input. Given a fixed source point s, we show how to construct a map, called a shortest k-path map, so that all destinations in the same region of the map have the same combinatorial shortest path passing through at most k obstacles. We prove a tight bound of $$\varTheta (kn)$$ on the size of this map, and show that it can be computed in $$O(k^2n \log n)$$ time, where n is the total number of obstacle vertices.