On Planar Visibility Counting Problem
share
For a set S of n disjoint line segments in ℝ^2, the visibility counting problem is to preprocess S such that the number of visible segments in S from any query point p can be computed quickly. There have been approximation algorithms for this problem with trade off between space and query time. We propose a new randomized algorithm to compute the exact answer of the problem. For any 0<α<1, the space, preprocessing time and query time are O_ϵ(n^4-4α), O_ϵ(n^4-2α) and O_ϵ(n^2α), respectively. Where O_ϵ(f(n)) = O(f(n)n^ϵ) and ϵ>0 is an arbitrary constant number.
READ FULL TEXT