Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
Danny Z. Chen, Kevin S. Klenk, Hung-Yi Tu · SIAM Journal on Computing · 2000
We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(nlog 3/2 n ) time and O(nlog n) space, where n is the number of obstacle vertices; this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n+ k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n 2 log 2 n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log 2 n ) time, and an actual shortest path in O(log 2 n + k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two-point L 1 shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known.