Approximation and randomized method for Visibility Counting Problem

For a set of n disjoint line segments S in R2, the visibility counting problem (VCP) is to preprocess S such that the number of visible segments in S from a query point p can be computed quickly. This problem can be solved in logarithmic query time using O(n4) preprocessing time and space. In this paper, we propose a randomized approximation algorithm for this problem. The space of our algorithm is O(n4􀀀3) and the query time is O(n). The complexity of our algorithm is superior compare to best known algorithm for this problem.