Shortest Paths in the Plane with Obstacle Violations

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 ≤ 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 (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.