Randomized approximation algorithms for planar visibility counting problem

In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0≤β≤23 and 0<δ≤1, and the expected preprocessing time, the expected space, and the expected query time are O(m2−3β/2log⁡m), O(m2−3β/2), and O(1δ2mβ/2log⁡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 mp, exactly, if mp≤3δ2mβ/2log⁡(2m). Otherwise, it computes an approximated value, mp′, such that with the probability of at least 1−1m, we have (1−δ)mp≤mp′≤(2+2δ)mp. The preprocessing time and space of the second algorithm are O(n2log⁡n) and O(n2), respectively. This algorithm computes the exact value of mp if mp≤1δ2nlog⁡n, otherwise it returns an approximated value mp″ in expected O(1δ2nlog⁡n) time, such that with the probability at least 1−1log⁡n, we have (1−3δ)mp≤mp″≤(1.5+3δ)mp.