2017/03/08 by Haitao Wang, Wang, Haitao
Computer Science · Engineering · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1703.03048
openalex publication_date 2017/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let s be a point in a polygonal domain P of h-1 holes and n vertices. We consider a quickest visibility query problem. Given a query point q in P, the goal is to find a shortest path in P to move from s to see q as quickly as possible. Previously, Arkin et al. (SoCG 2015) built a data structure of size O(n22α(n)log n) that can answer each query in O(Klog2 n) time, where α(n) is the inverse Ackermann function and K is the size of the visibility polygon of q in P (and K can be Θ(n) in the worst case). In this paper, we present a new data structure of size O(nlog h + h2) that can answer each query in O(hlog hlog n) time. Our result improves the previous work when h is relatively small. In particular, if h is a constant, then our result even matches the best result for the simple polygon case (i.e., h=1), 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 τ in P, the query seeks a shortest path from s to all points of τ. Previously, Arkin et al. gave a data structure of size O(n22α(n)log n) that can answer each query in O(log2 n) time, and another data structure of size O(n3log n) with O(log n) query time. We present a data structure of size O(n) with query time O(hlog (n)/(h)), which also favors small values of h and is optimal when h=O(1).