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.
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 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 consider shortest path queries in a polygonal domain Phaving nvertices and hholes. A skeleton graph is a subgraph of a Voronoi diagram of P. Our novel algorithm utilizes a reduced skeleton graph of Pto compute a tessellation of P. It builds a data structure of size O(n2) in O(n2logn) time to support distance queries for any pair of query points in Pin O(hlogn) 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.