Randomized approximation algorithms for planar visibility counting problem.

Given a set S of n disjoint line segments in R 2 , the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can be solved trivially in O ( log ⁡ n ) query time using O ( n 4 log ⁡ n ) preprocessing time and O ( n 4 ) space. Gudmundsson and Morin (2010) [10] proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. For any constant 0 ≤ α ≤ 1 , their algorithm answers any query in O ϵ ( m ( 1 − α ) / 2 ) time with O ϵ ( m 1 + α ) of preprocessing time and space, where ϵ > 0 is a constant that can be made arbitrarily small and O ϵ ( f ( n ) ) = O ( f ( n ) n ϵ ) and m = O ( n 2 ) is a number that depends on the configuration of the segments. In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0 ≤ β ≤ 2 3 and 0 < δ ≤ 1 , and the expected preprocessing time, the expected space, and the expected query time are O ( m 2 − 3 β / 2 log ⁡ m ) , O ( m 2 − 3 β / 2 ) , and O ( 1 δ 2 m β / 2 log ⁡ m ) , respectively. The algorithm, in the preprocessing phase, selects a sequence of random samples, whose size and number depend on the tradeoff parameters. When a query point p is given by an adversary unaware of the random sample of our algorithm, it computes the number of visible segments from p , denoted by m p , exactly, if m p ≤ 3 δ 2 m β / 2 log ⁡ ( 2 m ) . Otherwise, it computes an approximated value, m p ′ , such that with the probability of at least 1 − 1 m , we have ( 1 − δ ) m p ≤ m p ′ ≤ ( 2 + 2 δ ) m p . The preprocessing time and space of the second algorithm are O ( n 2 log ⁡ n ) and O ( n 2 ) , respectively. This algorithm computes the exact value of m p if m p ≤ 1 δ 2 n log ⁡ n , otherwise it returns an approximated value m p ″ in expected O ( 1 δ 2 n log ⁡ n ) time, such that with the probability at least 1 − 1 log ⁡ n , we have ( 1 − 3 δ ) m p ≤ m p ″ ≤ ( 1.5 + 3 δ ) m p . [ABSTRACT FROM AUTHOR]