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.

Authors

• Sharareh Alipour New Uzbekistan University
• Mohammad Ghodsi
• Amir Jafari

Keywords

• Computational geometry
• Visibility
• Randomized algorithm
• Approximation algorithm
• Graph theory