Visibility queries in a polygonal region

In this paper, we consider the problem of computing the region visible to a query point located in a given polygonal domain. The polygonal domain is specified by a simple polygon with m holes and a total of n vertices. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n2) in time O(n2lgn) and yields a query time of O((1+min(m,|V(q)|))lg2n+m+|V(q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, and |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|,mn)+n) in time O(T+|E|+nlgn) with the query time of O(|V(q)|lgn+m). Here, T is the time to triangulate the given polygonal region (which is O(n+mlg1+ϵm) for a small positive constant ϵ>0). In both of these approaches, O(m) additive factor in the query time is eliminated with an additional O((min2(|E|,mn))) space and an additional O(m(min2(|E|,mn))) preprocessing time.