Let @math be a set of @math pairwise-disjoint polygonal obstacles with a total of @math vertices in the plane. We consider the problem of building a data structure that can quickly compute an @math shortest obstacle-avoiding path between any two query points @math and @math . Previously, a data structure of size @math was constructed in @math time that answers each two-point query in @math time, i.e., the shortest path length is reported in @math time and an actual path is reported in additional @math time, where @math is the number of edges of the output path. In this paper, we build a new data structure of size @math in @math time that answers each query in @math time. Note that @math for any constant @math . Further, we extend our techniques to the weighted rectilinear version in which the "obstacles" of @math are rectilinear regions with "weights" and allow @math paths to travel through them with weighted costs. Our algorithm answers each query in @math time with a data structure of size @math that is built in @math time (note that @math for any constant @math ).
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. Given a triangulation of a simple polygonP, we present linear-time algorithms for solving a collection of problems concerning shortest paths and visibility withinP. These problems include calculation of the collection of all shortest paths insideP from a given source vertexS to all the other vertices ofP, calculation of the subpolygon ofP consisting of points that are visible from a given segment withinP, preprocessingP for fast "ray shooting" queries, and several related problems. 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. 