2016/05/11 by Sharareh Alipour, Mohammad Ghodsi, Alipour, Sharareh +4
Computer Science · #Computational Geometry and Mesh Generation #Optimization and Search Problems #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.1605.03542
Given a set S of n disjoint line segments in \ℝ2, the\nvisibility counting problem (VCP) is to preprocess S such that the number of\nsegments in S visible from any query point p can be computed quickly. This\nproblem can trivially be solved in logarithmic query time using O(n4)\npreprocessing time and space. Gudmundsson and Morin proposed a 2-approximation\nalgorithm for this problem with a tradeoff between the space and the query\ntime. They answer any query in O\ε(n1-\α) with\nO\ε(n2+2\α) of preprocessing time and space, where \α\nis a constant 0\≤ \α\≤ 1, \ε > 0 is another constant that can\nbe made arbitrarily small, and O\ε(f(n))=O(f(n)n\ε).\n In this paper, we propose a randomized approximation algorithm for VCP with a\ntradeoff between the space and the query time. We will show that for an\narbitrary constants 0\≤ \β\≤ \(2)/(3) and 0<\δ <1, the\nexpected preprocessing time, the expected space, and the query time of our\nalgorithm are O(n4-3\β\log n), O(n4-3\β), and\nO(\(1)/(\δ3)n\β\log n), respectively. The algorithm computes\nthe number of visible segments from p, or mp, exactly if mp\≤\n\(1)/(\δ3)n\β\log n. Otherwise, it computes a\n(1+\δ)-approximation m'p with the probability of at least\n1-\(1)/(\log n), where mp\≤ m'p\≤ (1+\δ)mp.\n