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 are also known for one-point queries in the @math metric @cite_13 @cite_9 @cite_18 @cite_25 @cite_6 @cite_17 , i.e., @math is fixed in the input and only @math is a query point. In particular, Mitchell @cite_6 @cite_17 built a data structure of @math size in @math time that can answer each such query in @math time. Later Chen and Wang @cite_13 reduced the preprocessing time to @math if @math is already triangulated (which can be done in @math or @math time for any @math @cite_0 @cite_5 ), while the query time is still @math .
@cite_18 @cite_9 @cite_6 @cite_0 @cite_5 @cite_13 @cite_25 @cite_17
1979832172 160239005 2171580054 2106413026 2963551506 2021380525 2063372577
The problem of finding a rectilinear shortest path amongst obstacles may be stated as follows: Given a set of obstacles in the plane find a shortest rectilinear ( L 1 ) path from a point s to a point t which avoids all obstacles. The path may touch an obstacle but may not cross an obstacle. We study the rectilinear shortest path problem for the case where the obstacles are non-intersecting simple polygons, and present an O ( n (log n ) 2 ) algorithm for finding such a path, where n is the number of vertices of the obstacles. We also study the case of rectilinear obstacles in three dimensions, and show that L 1 shortest paths can be found in O ( n 2 (log n ) 3 ) time. Recent advances on polygon triangulation have yielded efficient algorithms for a large number of problems dealing with a single simple polygon. If the input consists of several disjoint polygons, however, it is often desirable to merge them in preprocessing so as to produce a single polygon that retains the geometric characteristics of its individual components. We give an efficient method for doing so, which combines a generalized form of Jordan sorting with the efficient use of point location and interval trees. As a corollary, we are able to triangulate a collection of p disjoint Jordan polygonal chains in time O (n + p (log p)1+e), for any fixed e > 0, where n is the total number of vertices. A variant of the algorithm gives a running time of O ((n + p log p) log log p). The performance of these solutions approaches the lower bound of Ω (n + p log p). We give a deterministic algorithm for triangulating a simple polygon in linear time. The basic strategy is to build a coarse approximation of a triangulation in a bottom-up phase and then use the information computed along the way to refine the triangulation in a top-down phase. The main tools used are the polygon-cutting theorem, which provides us with a balancing scheme, and the planar separator theorem, whose role is essential in the discovery of new diagonals. Only elementary data structures are required by the algorithm. In particular, no dynamic search trees, of our algorithm. 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+h h) ) 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 (L_1 ) shortest obstacle-avoiding path from s to t can be computed in (O( n) ) 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(n n) ) 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 (L_1 ) geodesic Voronoi diagram for a set of point sites among the obstacles. The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest L"1-metric (rectilinear) path from a point s to a point t that avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n+m(lgn)^3^ ^2), which is close to the known lower bound of @W(n+mlgm) for finding such a path. Here, n is the number of vertices of all the obstacles together. We present an algorithm for computingL1 shortest paths among polygonal obstacles in the plane. Our algorithm employs the "continuous Dijkstra" technique of propagating a "wavefront" and runs in timeO(E logn) and spaceO(E), wheren is the number of vertices of the obstacles andE is the number of "events." By using bounds on the density of certain sparse binary matrices, we show thatE =O(n logn), implying that our algorithm is nearly optimal. We conjecture thatE =O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding anO(nźź1 2 log2n) time andO(nźź1 2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute anL1 Voronoi diagram for source points that lie among a collection of polygonal obstacles.