2026-08-18T23:34:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7186 2024-03-06T10:40:04Z ddc:004 open_access

Quickest Visibility Queries in Polygonal Domains Wang, Haitao shortest paths visibility quickest visibility queries shortest path to segments polygons with holes Let s be a point in a polygonal domain P of h-1 holes and n vertices. We consider the following 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(n^2 2^alpha(n) log n) that can answer each query in O(K log^2 n) time, where alpha(n) is the inverse Ackermann function and K is the size of the visibility polygon of q in P (and K can be Theta(n) in the worst case). In this paper, we present a new data structure of size O(n log h + h^2) that can answer each query in O(h log h log 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 the following shortest-path-to-segment query problem. Given a query line segment tau in P, the query seeks a shortest path from s to all points of tau. Previously, Arkin et al. gave a data structure of size O(n^2 2^alpha(n) log n) that can answer each query in O(log^2 n) time, and another data structure of size O(n^3 log n) with O(log n) query time. We present a data structure of size O(n) with query time O(h log n/h), which favors small values of h and is optimal when h = O(1). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.61 urn:nbn:de:0030-drops-71863 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.61 eng https://creativecommons.org/licenses/by/3.0/legalcode