In this paper the authors address the following shortest-path problem. Given a point in the plane and n disjoint isothetic rectangles (barriers), they want to construct a shortest L1 path (not crossing any of the barriers) from the source point to any given query point. A restricted version of this problem (where the source and destination points are known a priori) had been solved earlier in O(n2) time. The present approach consists of preprocessing the source point and the barriers to obtain a planar subdivision where a query point can be located and a shortest path connecting it to the source point quickly transvered. By showing that any such path is monotone in at least one of x or y directions, the authors are able to apply a plane sweep technique to divide the plane into O(n) rectangular regions. This leads to an algorithm whose complexity is O(nlogn) preprocessing time, O(n) space, and O(logn+k) query time, where k is the number of turns on the reported path. If only the length of the path is sought, O(logn) query time suffices. Furthermore, the authors show an ¦[(nlogn) time lower bound for the case where the source and destination points are known in advance, which implies the optimality of the present algorithm in this case.
