An improved Constant-Factor Approximation Algorithm for Planar Visibility Counting Problem
Sharareh Alipour, Mohammad Ghodsi, Amir Jafari · arXiv (Cornell University) · 2016
Given a set $S$ of $n$ disjoint line segments in $\mathbb{R}^{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(n^{4})$ 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_ε(n^{1-α})$ with $O_ε(n^{2+2α})$ of preprocessing time and space, where $α$ is a constant $0\leq α\leq 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\leq β\leq \frac{2}{3}$ and $0