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_11: We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortest-path-to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a different generalization of shortest-path-to-a-point queries, which may be of independent interest: to report efficiently a shortest path from s to a query segment in the domain.
For the quickest visibility queries, @cite_11 also built a quickest visibility map'' of @math size in @math time, which can answer each query in @math time. In addition, @cite_11 gave a conditional lower bound on the problem by showing that the 3SUM problem on @math numbers can be solved in @math time, where @math is the preprocessing time and @math is the query time. Therefore, a data structure of @math preprocessing time and @math query time would lead to an @math time algorithm for 3SUM.