Computing L_1 Shortest Paths Among Polygonal Obstacles in the Plane

摘要

Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, suppose a triangulation of the space outside the obstacles is given; we present an O(n+hlogh) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of an L1 shortest obstacle-avoiding path from s to t can be computed in O(logn) time and the actual path can be reported in additional time proportional to the number of edges of the path. The previously best algorithm computes such a shortest path map in O(nlogn) time and O(n) space. So our algorithm is faster when h is relatively small. Further, our techniques can be extended to obtain improved results for other related problems, e.g., computing the L1 geodesic Voronoi diagram for a set of point sites among the obstacles.