On Planar Visibility Counting Problem

Abstract

For a set $S$ of $n$ disjoint line segments in ${\mathbb{R}}^2$, the visibility counting problem is to preprocess $S$ such that the number of visible segments in $S$ from any query point $p$ can be computed quickly. There have been approximation algorithms for this problem with trade off between space and query time. We propose a new randomized algorithm to compute the exact answer of the problem. For any $0<\alpha <1$, the space, preprocessing time and query time are $O_{\epsilon }(n^{4-4\alpha })$, $O_{\epsilon }(n^{4-2\alpha })$ and $O_{\epsilon }(n^{2\alpha })$, respectively. Where $O_{\epsilon }(f(n))=O(f(n)n^{\epsilon })$ and $\epsilon >0$ is an arbitrary constant number.

References in corpus (1)

• Planar Visibility Counting