Article ID Journal Published Year Pages File Type
6875721 Theoretical Computer Science 2018 16 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,