Let @math be a polygonal domain of @math holes and @math vertices. We study the problem of constructing a data structure that can compute a shortest path between @math and @math in @math under the @math metric for any two query points @math and @math . To do so, a standard approach is to first find a set of @math "gateways" for @math and a set of @math "gateways" for @math such that there exist a shortest @math - @math path containing a gateway of @math and a gateway of @math , and then compute a shortest @math - @math path using these gateways. Previous algorithms all take quadratic @math time to solve this problem. In this paper, we propose a divide-and-conquer technique that solves the problem in @math time. As a consequence, we construct a data structure of @math size in @math time such that each query can be answered in @math time.
Better results exist for certain special cases of the problem. If @math is a simple polygon, then a shortest path in @math with minimum Euclidean length is also an @math shortest path @cite_24 , and thus by using the data structure in @cite_15 @cite_2 for the Euclidean metric, one can build a data structure in @math time and space that can answer each query in @math time; recently Bae and Wang @cite_16 proposed a simpler approach that can achieve the same performance. If @math and all holes of it are rectangles whose edges are all axis-parallel, then ElGindy and Mitra @cite_4 constructed a data structure of @math size in @math time that supports @math time queries.
@cite_4 @cite_24 @cite_2 @cite_15 @cite_16
2118838969 2031247977 1989723858 2113370909
We present a data structure that allows to preprocess a rectilinear polygon with n vertices such that, for any two query points, the shortest path in the rectilinear link or L1-metric can be reported in time O(log n+k) where k is the link length of the shortest path. If only the distance is of interest, the query time reduces to O(log n). Furthermore, if the query points are two vertices, the distance can be reported in time O(1) and a shortest path can be constructed in time O(1+k). The data structure can be computed in time O(n) and needs O(n) storage. As an application we present a linear time algorithm to compute the diameter of a simple rectilinear polygon w.r.t. the L1-metric. We consider the two-point query version of the fundamental geometric shortest path problem: Given a set h of polygonal obstacles iu the plane, having a total of n vertices, build a data structure such that for any two query points s and t we can efficiently determine the length, d(s,t), of an Euclidean shortest obstacle-avoiding path, *(s,t), from s to t. Additionally, our data structure should allow one to report the path x(s, t), in time proportional to its (combinatorial) size. We present various methods for solving this two-point query problem, including algorithms with o(n), O(log n+h), 0( h log n), O(log’ n) or optimal O(log n) query times, using polynomial-space data structures, with various tradeoffs between space and query time. While severa results have been known for approtimate twepoint Euclidean shortest path queries, it has been a well-publicized open problem to obtain sublinear query time for the exact version of the problem. Our methods also yield data structures for twc+point shortest path queries on nonconvex polyhedral 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. In this paper we study two link distance problems for rectilinear paths inside a simple rectilinear polygon P.First, we present a data structure using O(n log n) storage such that a shortest path between two query points can be computed efficiently. If both query points are vertices of P, the query time is O(1 + l), where l is the number of links. If the query points are arbitrary points inside P, then the query time becomes O(log n + l). The resulting path is not only optimal in the rectilinear link metric, but it is optimal in the L1-metric as well. Secondly, it is shown that the rectilinear link diameter of P can be computed in time O(n log n). We also give an approximation algorithm that runs in linear time. This algorithm produces a solution that differs by at most three links from the exact diameter.The solutions are based on a rectilinear version of Chazelle's polygon cutting theorem. This new theorem states that any simple rectilinear polygon can be cut into two rectilinear subpolygons of size at most 34 times the original size, and that such a cut segment can be found in linear time.