Obstacle-avoiding path-existence queries in a simple polygon

Matthew Eastman

Let P be a simple polygon with n vertices. We will show how to preprocess the polygon so that, given two query points s and t, and a convex polygon Q with m vertices, we can determine in O(m log³n) time whether there exists a path from s to t in P \ Q. If such a path exists then the shortest path between s and t in P \ Q can be found in O(m log³n + k) time, where k is the number of segments in the shortest path.