Loading...

An improved constant-factor approximation algorithm for planar visibility counting problem

Alipour, S ; Sharif University of Technology | 2016

932 Viewed
  1. Type of Document: Article
  2. DOI: 10.1007/978-3-319-42634-1_17
  3. Publisher: Springer Verlag , 2016
  4. Abstract:
  5. Given a set S of n disjoint line segments in ℝ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 trivially be solved in logarithmic query time using O(n4) preprocessing time and space. Gudmundsson and Morin proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. They answer any query in Oε(n1−α) with Oε(n2+2α) of preprocessing time and space, where α is a constant 0 ≤ α ≤ 1, ε > 0 is another constant that can be made arbitrarily small, and Oε(f(n)) = O(f(n)nε). In this paper, we propose a randomized approximation algorithm for VCP with a tradeoff between the space and the query time. We will show that for an arbitrary constants 0 ≤ β ≤ 2/3 and 0 < δ < 1, the expected preprocessing time, the expected space, and the query time of our algorithm are O(n4−3β log n), O(n4−3β), and O(1/δ3 nβ log n), respectively. The algorithm computes the number of visible segments from p, or mp, exactly if mp ≤ 1/δ3 nβ log n. Otherwise, it computes a (1+δ)-approximation m′p with the probability of at least 1−1/log n, where mp ≤ m′p ≤ (1 + δ)mp
  6. Keywords:
  7. Approximation algorithm ; Randomized algorithm ; Algorithms ; Combinatorial mathematics ; Computation theory ; Computational geometry ; Graph theory ; Query processing ; Visibility ; Arbitrary constants ; Constant-factor approximation algorithms ; Counting problems ; Line segment ; Preprocessing time ; Query points ; Randomized Algorithms ; Randomized approximation ; Approximation algorithms
  8. Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2 August 2016 through 4 August 2016 ; Volume 9797 , 2016 , Pages 209-221 ; 03029743 (ISSN) ; 9783319426334 (ISBN)
  9. URL: https://link.springer.com/chapter/10.1007%2F978-3-319-42634-1_17