Given a rectilinear domain @math of @math pairwise-disjoint rectilinear obstacles with a total of @math vertices in the plane, we study the problem of computing bicriteria rectilinear shortest paths between two points @math and @math in @math . Three types of bicriteria rectilinear paths are considered: minimum-link shortest paths, shortest minimum-link paths, and minimum-cost paths where the cost of a path is a non-decreasing function of both the number of edges and the length of the path. The one-point and two-point path queries are also considered. Algorithms for these problems have been given previously. Our contributions are threefold. First, we find a critical error in all previous algorithms. Second, we correct the error in a not-so-trivial way. Third, we further improve the algorithms so that they are even faster than the previous (incorrect) algorithms when @math is relatively small. For example, for the minimum-link shortest paths, we obtain the following results. Our algorithm computes a minimum-link shortest @math - @math path in @math time. For the one-point queries, we build a data structure of size @math in @math time for a source point @math , such that given any query point @math , a minimum-link shortest @math - @math path can be determined in @math time. For the two-point queries, with @math time and space preprocessing, a minimum-link shortest @math - @math path can be determined in @math time for any two query points @math and @math ; alternatively, with @math time and @math space preprocessing, we can answer each two-point query in @math time.
To find a minimum-link path between two points @math and @math in an arbitrary polygonal domain @math , Mitchell @cite_8 gave an @math time algorithm, where @math is the inverse of Ackermann's function and @math is the size of the visibility graph of @math and @math in the worst case. The one-point query problem was also studied in @cite_8 .
@cite_8
2020449301 1583742799 2113370909 2107704676 2031247977 1985010089 1989723858 2233662001 2058510050 2167427782 1990187919 1782245179 150506545 2003711654 2949937035 2568372686 2963551506 2063372577 2004779317 1481010420
Given a set of nonintersecting polygonal obstacles in the plane, thelink distance between two pointss andt is the minimum number of edges required to form a polygonal path connectings tot that avoids all obstacles. We present an algorithm that computes the link distance (and a corresponding minimum-link path) between two points in timeO(Eź(n) log2n) (and spaceO(E)), wheren is the total number of edges of the obstacles,E is the size of the visibility graph, and ź(n) denotes the extremely slowly growing inverse of Ackermann's function. We show how to extend our method to allow computation of a tree (rooted ats) of minimum-link paths froms to all obstacle vertices. This leads to a method of solving the query version of our problem (for query pointst). We present an algorithm to find an Euclidean Shortest Path from a source vertex @math to a sink vertex @math in the presence of obstacles in @math . Our algorithm takes @math time and @math space. Here, @math is the time to triangulate the polygonal region, @math is the number of obstacles, and @math is the number of vertices. This bound is close to the known lower bound of @math time and @math space. Our approach involve progressing shortest path wavefront as in continuous Dijkstra-type method, and confining its expansion to regions of interest. 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. In this paper, we study several geometric path query problems. Given a scene of disjoint polygonal obstacles with totally n vertices in the plane, we construct efficient data structures that enable fast reporting of an "optimal" obstacle-avoiding path (or its length, cost, directions, etc) between two arbitrary query points s and t that are given in an on-line fashion. We consider geometric paths under several optimality criteria: Lm length, number of edges (called links), monotonicity with respect to a certain direction, and some combinations of length and links. Our methods are centered around the notion of gateways, a small number of easily identified points in the plane that control the paths we seek. We give efficient solutions for several special cases based upon new geometric observations. We also present solutions for the general cases based upon the computation of the minimum size visibility polygon for query points. 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 We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required O(n 2 log n) time and O (n 2 ) space, where n denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in O ( n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s , produces an O(n) size data structure such that the distance between s and any other point x in the plane ( x ) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in O (1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk). 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 present a new algorithm for finding minimum-link rectilinear paths among h rectilinear obstacles with a total of n vertices in the plane. After the plane is triangulated, for any point s, our algorithm builds an O(n)-size data structure in (O(n+h h) ) time, such that given any query point t, we can compute a minimum-link rectilinear path from s to t in (O( n+k) ) time, where k is the number of edges of the path, and the query time is (O( n) ) if we only want to know the value k. The previously best algorithm solves the problem in (O(n n) ) time. We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs in worst-case time O(n log n) and requires O(n log n) space, where n is the total number of vertices in the obstacle polygons. The algorithm is based on an efficient implementation of wavefront propagation among polygonal obstacles, and it actually computes a planar map encoding shortest paths from a fixed source point to all other points of the plane; the map can be used to answer single-source shortest path queries in O(log n) time. The time complexity of our algorithm is a significant improvement over all previously published results on the shortest path problem. Finally, we also discuss extensions to more general shortest path problems, involving nonpoint and multiple sources. We give a subquadratic (O(n3 2+∊) time and O(n) space) algorithm for computing Euclidean shortest paths in the plane in the presence of polygonal obstacles; previous time bounds were at least quadratic in n, in the worst case. The method avoids use of visibility graphs, relying instead on the continuous Dijkstra paradigm. The output is a shortest path map (of size O(n)) with respect to a given source point, which allows shortest path length queries to be answered in time O(log n). The algorithm extends to the case of multiple source points, yielding a method to compute a Voronoi diagram with respect to the shortest path metric. A path or a polygonal domain is C-oriented if the orientations of its edges belong to a set of C given orientations; this is a generalization of the notable rectilinear case ( C = 2 ). We study exact and approximation algorithms for minimum-link C-oriented paths and paths with unrestricted orientations, both in C-oriented and in general domains.Our two main algorithms are as follows:A subquadratic-time algorithm with a non-trivial approximation guarantee for general (unrestricted-orientation) minimum-link paths in general domains.An algorithm to find a minimum-link C-oriented path in a C-oriented domain. Our algorithm is simpler and more time-space efficient than the prior algorithm.We also obtain several related results:3SUM-hardness of determining the link distance with unrestricted orientations (even in a rectilinear domain).An optimal algorithm for finding a minimum-link rectilinear path in a rectilinear domain. The algorithm and its analysis are simpler than the existing ones.An extension of our methods to find a C-oriented minimum-link path in a general (not necessarily C-oriented) domain.A more efficient algorithm to compute a 2-approximate C-oriented minimum-link path.A notion of "robust" paths. We show how minimum-link C-oriented paths approximate the robust paths with unrestricted orientations to within an additive error of 1. We study the aggregate group nearest neighbor searching for the MAX operator in the plane. For a set @math of @math points and a query set @math of @math points, the query asks for a point of @math whose maximum distance to the points in @math is minimized. We present data structures for answering such queries for both @math and @math distance measures. Previously, only heuristic and approximation algorithms were given for both versions. For the @math version, we build a data structure of O(n) size in @math time, such that each query can be answered in @math time. For the @math version, we build a data structure in @math time and @math space, such that each query can be answered in @math time, and alternatively, we build a data structure in @math time and space for any @math , such that each query can be answered in @math time. Further, we extend our result for the @math version to the top- @math queries where each query asks for the @math points of @math whose maximum distances to @math are the smallest for any @math with @math : We build a data structure of O(n) size in @math time, such that each top- @math query can be answered in @math time. In this paper, we study the problem of finding the shortest path from a given source point in a simple polygon to some point visible from a given query point. We will present an algorithm based on the notion of funnels in simple polygons. The algorithm preprocesses the input containing a simple polygon and a source point to produce a data structure to answer the queries in logarithmic time. The time and space required for preprocessing is quadratic in size of the simple polygon. The problem of determining the Euclidean shortest path between two points in the presence of m simple polygonal obstacles is studied. An O( m 2 logn + nlogn ) algorithm is developed, where n is the total number of points in the obstacles. A simple O(E+T) algorithm for determining the visibility graph is also shown, where E is the number of visibility edges and T is the time for triangulating the point set. This is extended to a O(E s + nlogn) algorithm for the shortest path problem where E s is bounded by m 2 . Let @math be a simple polygon of @math vertices. We consider two-point @math shortest path queries in @math . We build a data structure of @math size in @math time such that given any two query points @math and @math , the length of an @math shortest path from @math to @math in @math can be computed in @math time, or in @math time if both @math and @math are vertices of @math , and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem. Given n points in a circular region C in the plane, we study the problem of moving these points to the boundary of C to form a regular n-gon such that the maximum of the Euclidean distances traveled by the points is minimized. These problems find applications in mobile sensor barrier coverage of wireless sensor networks. The problem further has two versions: the decision version and optimization version. In this paper, we present an O(nlog2 n) time algorithm for the decision version and an O(nlog3 n) time algorithm for the optimization version. The previously best algorithms for these two problem versions take O(n 3.5) time and O(n 3.5logn) time, respectively. A by-product of our techniques is an algorithm for dynamically maintaining the maximum matching of a circular convex bipartite graph; our algorithm performs each vertex insertion or deletion on the graph in O(log2 n) time. This result may be interesting in its own right. 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. 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. For a graph G and a collection of vertex pairs (s"1,t"1),...,(s"k,t"k) , the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P"i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3. Min-Sum: We extend recent results by Colin de Verdiere and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time. Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3. We consider the problem of finding an obstacle-avoiding path between two points s and t in the plane, amidst a set of disjoint polygonal obstacles with a total of n vertices. The length of this path should be within a small constant factor c of the length of the shortest possible obstacle-avoiding s-t path measured in the L p -metric. Such an approximate shortest path is called a c-short path, or a short path with stretch factor c. The goal is to preprocess the obstacle-scattered plane by creating an efficient data structure that enables fast reporting of a c-short path (or its length). In this paper, we give a family of algorithms for the above problem that achieve an interesting trade-off between the stretch factor, the query time and the preprocessing bounds. Our main results are algorithms that achieve logarithmic length query time, after subquadratic time and space preprocessing.