انجمن کامپیوتر ایران

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