Visibility Queries in Simple Polygons

Given a simple polygon $P$ with $n$ vertices, we consider the problem of constructing a data structure for visibility queries: for any query point $q\in P$, compute the visibility polygon of $q$ in $P$. To obtain $O(\log n+k)$ query time, where $k$ is the size of the visibility polygon of $q$, the previous best result requires $O(n^3)$ space. In this paper, we propose a new data structure that uses $O(n^{2+\epsilon })$ space, for any $\epsilon >0$, while achieving the same query time. If only $O(n^2)$ space is available, the best known result provides $O({\log }^{2}n+k)$ query time. We improve this to $O(\log n\log \log n+k)$ time. When restricted to $o(n^2)$ space, the only previously known approach, aside from the $O(n)$-time algorithm that computes the visibility polygon without preprocessing, is an $O(n)$-space data structure that supports $O(k\log n)$-time queries. We construct a data structure using $O(n\log n)$ space that answers visibility queries in $O(n^{1\mathrm{/}2+\epsilon }+k)$ time. In addition, for the special case in which $q$ lies on the boundary of $P$, we build a data structure of $O(n\log n)$ space supporting $O({\log }^{2}n+k)$ query time; alternatively, we achieve $O(\log n+k)$ query time using $O(n^{1+\epsilon })$ space. To achieve our results, we propose a new method for decomposing simple polygons, which may be of independent interest.