Query-point visibility constrained shortest paths in simple polygons

In this paper, we study the problem of finding the shortest path between two points inside a simple polygon such that there is at least one point on the path from which a query point is visible. We provide an algorithm which preprocesses the input in O(n(2) + n(K)) time and space and provides logarithmic query time. The input polygon has n vertices and K is a parameter dependent on the input polygon which is O(n(2)) in the worst case but is much smaller for most polygons. The preprocessing algorithm sweeps an angular interval around every reflex vertex of the polygon to store the optimal contact points between the shortest paths and the windows separating the visibility polygons of the query points from the source and the destination. (c) 2007 Elsevier B.V. All rights reserved.