Let @math be a point in a polygonal domain @math of @math holes and @math vertices. We consider a quickest visibility query problem. Given a query point @math in @math , the goal is to find a shortest path in @math to move from @math to see @math as quickly as possible. Previously, (SoCG 2015) built a data structure of size @math that can answer each query in @math time, where @math is the inverse Ackermann function and @math is the size of the visibility polygon of @math in @math (and @math can be @math in the worst case). In this paper, we present a new data structure of size @math that can answer each query in @math time. Our result improves the previous work when @math is relatively small. In particular, if @math is a constant, then our result even matches the best result for the simple polygon case (i.e., @math ), which is optimal. As a by-product, we also have a new algorithm for a shortest-path-to-segment query problem. Given a query line segment @math in @math , the query seeks a shortest path from @math to all points of @math . Previously, gave a data structure of size @math that can answer each query in @math time, and another data structure of size @math with @math query time. We present a data structure of size @math with query time @math , which also favors small values of @math and is optimal when @math .
@cite_24: 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.
@cite_25: 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.
@cite_8: 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.
The traditional shortest path query problem has been studied extensively, which is to compute a shortest path to move from @math to reach'' a query point. Each shortest path query can be answered in @math time by using the shortest path map of @math , denoted by @math , which is of @math size. To build @math , Mitchell @cite_8 gave an algorithm of @math time for any @math and @math space, and later Hershberger and Suri @cite_24 presented an algorithm of @math time and space. If @math is a simple polygon (i.e., @math ), @math can be built in @math time, e.g., see @cite_25 .