Planar visibility: Testing and counting
In this paper we consider query versions of visibility testing and visibility counting. Let S be a set of n disjoint line segments in ℝ2 and let s be an element of S. Visibility testing is to preprocess S so that we can quickly determine if s is visible from a query point q. Visibility counting involves preprocessing S so that one can quickly estimate the number of segments in S visible from a query point q. We present several data structures for the two query problems. The structures build upon a result by O'Rourke and Suri (1984) who showed that the subset, VS(s), of ℝ2 that is weakly visible from a segment s can be represented as the union of a set, CS(s), of O(n2) triangles, even though the complexity of VS(s) can be Ω(n 4). We define a variant of their covering, give efficient output-sensitive algorithms for computing it, and prove additional properties needed to obtain approximation bounds. Some of our bounds rely on a new combinatorial result that relates the number of segments of S visible from a point p to the number of triangles in ∪s∈S CS(s) that contain p.
|Keywords||Geometric data structures, Visibility|
|Conference||26th Annual Symposium on Computational Geometry, SoCG 2010|
Gudmundsson, J. (Joachim), & Morin, P. (2010). Planar visibility: Testing and counting. Presented at the 26th Annual Symposium on Computational Geometry, SoCG 2010. doi:10.1145/1810959.1810973