Let @math be a set of @math pairwise-disjoint polygonal obstacles with a total of @math vertices in the plane. We consider the problem of building a data structure that can quickly compute an @math shortest obstacle-avoiding path between any two query points @math and @math . Previously, a data structure of size @math was constructed in @math time that answers each two-point query in @math time, i.e., the shortest path length is reported in @math time and an actual path is reported in additional @math time, where @math is the number of edges of the output path. In this paper, we build a new data structure of size @math in @math time that answers each query in @math time. Note that @math for any constant @math . Further, we extend our techniques to the weighted rectilinear version in which the "obstacles" of @math are rectilinear regions with "weights" and allow @math paths to travel through them with weighted costs. Our algorithm answers each query in @math time with a data structure of size @math that is built in @math time (note that @math for any constant @math ).
For the weighted region case, in which the obstacles" allow paths to pass through their interior with weighted costs, Mitchell and Papadimitriou @cite_19 gave an algorithm that finds a weighted Euclidean shortest path in a time of @math times a factor related to the precision of the problem instance. For the weighted rectilinear case, Lee al @cite_25 presented two algorithms for finding a weighted @math shortest path, and Chen al @cite_20 gave an improved algorithm with @math time and @math space. Chen al @cite_20 also presented a data structure for two-point weighted @math shortest path queries among weighted rectilinear obstacles, as mentioned above.
@cite_19 @cite_25 @cite_20
1989723858 2147998016 1992176147
The problem of determining shortest paths through a weighted planar polygonal subdivision with n vertices is considered. Distances are measured according to a weighted Euclidean metric: The length of a path is defined to be the weighted sum of (Euclidean) lengths of the subpaths within each region. An algorithm that constructs a (restricted) “shortest path map” with respect to a given source point is presented. The output is a partitioning of each edge of the subdivion into intervals of e-optimality, allowing an e-optimal path to be traced from the source to any query point along any edge. The algorithm runs in worst-case time O ( ES ) and requires O ( E ) space, where E is the number of “events” in our algorithm and S is the time it takes to run a numerical search procedure. In the worst case, E is bounded above by O ( n 4 ) (and we give an O( n 4 ) lower bound), but it is likeky that E will be much smaller in practice. We also show that S is bounded by O ( n 4 L ), where L is the precision of the problem instance (including the number of bits in the user-specified tolerance e). Again, the value of S should be smaller in practice. The algorithm applies the “continuous Dijkstra” paradigm and exploits the fact that shortest paths obey Snell's Law of Refraction at region boundaries, a local optimaly property of shortest paths that is well known from the analogous optics model. The algorithm generalizes to the multi-source case to compute Voronoi diagrams. We consider a rectilinear shortest path problem among weighted obstacles. Instead of restricting a path to totally avoid obstacles we allow a path to pass through them at extra costs. The extra costs are represented by the weights of the obstacles. We aim to find a shortest rectilinear path between two distinguished points among a set of weighted obstacles. The unweighted case is a special case of this problem when the weight of each obstacle is +∞. By using a graph-theoretical approach, we obtain two algorithms which run in O(n log2 n) time and O(n log n) space and in O(n log3 2 n) time and space, respectively, where n is the number of the vertices of the obstacles. 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(nlog3 2n) 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(n2 log2n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log2 n) time, and an actual shortest path in O(log2 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 L1 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.