Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875721 | Theoretical Computer Science | 2018 | 16 Pages |
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
Sharareh Alipour, Mohammad Ghodsi, Amir Jafari,