Weak visibility counting in simple polygons

For a simple polygon P of size n, we define weak visibility counting problem (WVCP) as finding the number of visible segments of P from a query line segment pq. We present different algorithms to compute WVCP in sub-linear time. In our first algorithm, we spend O(n(7)) time to preprocess the polygon and build a data structure of size O(n(6)), so that we can optimally answer WVCP in O(log n) time. Then, we reduce the preprocessing costs to O(n(4+epsilon)) time and space at the expense of more query time of O(log(5) n). We also obtain a trade-off between preprocessing and query time costs. Finally, we propose an approximation method to reduce the preprocessing costs to O(n(2)) time and space and O(n(1/2+epsilon)) query time. (C) 2015 Elsevier B.V. All rights reserved.