Weak visibility counting in simple polygons

• Studying weak visibility counting problem for line segments in simple polygons.
• Presenting several exact algorithms, and showing a trade-off between preprocessing costs and query time costs.
• Presenting an approximation algorithm for the problem, and reducing preprocessing costs.

For a simple polygon PP of size nn, we define weak visibility counting problem (WVCP) as finding the number of visible segments of PP from a query line segment pqpq. We present different algorithms to compute WVCP in sub-linear time. In our first algorithm, we spend O(n7)O(n7) time to preprocess the polygon and build a data structure of size O(n6)O(n6), so that we can optimally answer WVCP in O(logn)O(logn) time. Then, we reduce the preprocessing costs to O(n4+ϵ)O(n4+ϵ) time and space at the expense of more query time of O(log5n)O(log5n). 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(n2)O(n2) time and space and O(n1/2+ϵ)O(n1/2+ϵ) query time.