Weak visibility queries of line segments in simple polygons and polygonal domains
Mojtaba Nouri Bygi, Mohammad Ghodsi · International Journal of Computer Mathematics · 2017
In this paper we consider the problem of computing the weak visibility polygon of a query line segment pq (or WVP(pq)) inside a given polygon P. Our first algorithm runs in simple polygons and needs O(n3logn) time and O(n3) space in the preprocessing phase to report WVP(pq) of any query line segment pq in time O(logn+|WVP(pq)|). We also give an algorithm to compute the weak visibility polygon of a query line segment in a non-simple polygon with h≥1 pairwise-disjoint polygonal obstacles with a total of n vertices. Our algorithm needs O(n2logn) time and O(n2) space in the preprocessing phase and WVP(pq) in query time of O(nh′logn+k), in which h′ is an output sensitive parameter of at most min(h,k), and k=O(n2h2) is the output size.