Visibility testing and counting

• Given a set of n disjoint line segments and a segment s, we consider 2 problems.
• Visibility testing problem is to check whether a given point p is visible to s.
• Visibility counting problem is to count the number of segments visible from p.
• We give a new randomized algorithm for VTP and an approximation algorithm for VCP.
• We present our experimental results.

For a set of n disjoint line segments S   in R2R2, the visibility testing problem (VTP) is to test whether the query point p   sees a query segment s∈Ss∈S. For this configuration, the visibility counting problem (VCP) is to preprocess S such that the number of visible segments in S from any query point p   can be computed quickly. In this paper, we solve VTP in expected logarithmic query time using quadratic preprocessing time and space. Moreover, we propose a (1+δ)(1+δ)-approximation algorithm for VCP using at most quadratic preprocessing time and space. The query time of this method is Oϵ(1δ2n) where Oϵ(f(n))=O(f(n)nϵ)Oϵ(f(n))=O(f(n)nϵ) and ϵ>0ϵ>0 is an arbitrary constant number.