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.
Given a set ℬ of n barriers, the shortest route query SRQ problem asks for a preprocessing of ℬ such that a description of the shortest route between two points (origin and destination) can be reported efficiently. In this manuscript we present efficient sequential and parallel algorithms for the SRQ problem where the barriers in ℬ are disjoint planar rectangles whose sides are parallel to the coordinate axes, and subsequent queries ask for the shortest L1 route between two arbitrary points which avoids the barriers in ℬ. The segments forming such route are also restricted to be parallel to the coordinate axes. For this problem we we present sequential and parallel preprocessing algorithms which allow for reporting the shortest distance between two arbitrary query points in O(log n) time with a single processor. The route itself can also be constructed in time proportional to its number of segments. Our method is based on constructing three planar graphs, called carrier graphs, that contain the shortest route information in a succinct form. Each graph can then be searched using graph theoretic techniques. Using the same techniques we also present a parallel algorithm for computing the orthogonal shortest distance between two points among rectangular obstacles which runs in poly-logarithmic time using sub-quadratic number of processors on the CREW PRAM model of computation. Abstract In this paper, we show that the universal covering space of a surface can be used to unify previous results on computing paths in a simple polygon. We optimize a given path among obstacles in the plane under the Euclidean and link metrics and under polygonal convex distance functions. Besides revealing connections between the minimum paths under these three distance functions, the framework provided by the universal cover leads to simplified linear-time algorithms for shortest path trees, for minimum-link paths in simple polygons, and for paths restricted to c given orientations. Abstract This note describes a new data structure for answering shortest path queries inside a simple polygon. The new data structure has the same asymptotic performance as the previously known data structure (linear preprocessing after triangulation, logarithmic query time), but it is significantly less complicated. Abstract Let P be a simple polygon with n sides. This paper shows how to preprocess the polygon so that, given two query points p and q inside P , the length of the shortest path inside the polygon from p to q can be found in time O (log n ). The path itself must be polygonal and can be extracted in additional time proportional to the number of turns it makes. The preprocessing consists of triangulation plus a linear amount of additional work. 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.