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
2147998016 1992176147 1989723858 2268320119
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. 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. Problems related to computing optimal paths have been abundant in computer science since its emergence as a field. Yet for a large number of such problems we still do not know whether the state-of-the-art algorithms are the best possible. A notable example of this phenomenon is the all pairs shortest paths problem in a directed graph with real edge weights. The best algorithm (modulo small polylogarithmic improvements) for this problem runs in cubic time, a running time known since the 1960s (by Floyd and Warshall). Our grasp of many such fundamental algorithmic questions is far from optimal, and the major goal of this thesis is to bring some new insights into efficiently solving path problems in graphs. We focus on several path problems optimizing different measures: shortest paths, maximum bottleneck paths, minimum nondecreasing paths, and various extensions. For the all-pairs versions of these path problems we use an algebraic approach. We obtain improved algorithms using reductions to fast matrix multiplication. For maximum bottleneck paths and minimum nondecreasing paths we are the first to break the cubic barrier, obtaining truly subcubic strongly polynomial algorithms. We also consider a nonalgebraic, combinatorial approach, which is considered more efficient in practice compared to methods based on fast matrix multiplication. We present a combinatorial data structure that maintains a matrix so that products with given sparse vectors can be computed efficiently. This allows us to obtain good running times for path problems in unweighted sparse graphs. This thesis also gives algorithms for some single source path problems. We obtain the first linear time algorithm for the single source minimum nondecreasing paths problem. We give some extensions to this, including an algorithm to find cheapest minimum nondecreasing paths. Besides finding optimal paths, we consider the related problem of finding optimal cycles. In particular, we focus on the problem of finding in a weighted graph a triangle of maximum weight sum. We obtain the first truly subcubic algorithm for finding a maximum weight triangle in a node-weighted graph. We also present algorithms for the edge-weighted case. These algorithms immediately imply good algorithms for finding maximum weight k-cliques, or arbitrary maximum weight pattern subgraphs of fixed size.