Planar Visibility: Testing and Counting

Original · EN

In this paper we consider query versions of visibility testing and visibility counting. Let S be a set of n disjoint line segments in ² 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, Vₛ(s), of ² that is weakly visible from a segment s can be represented as the union of a set, Cₛ(s), of O(n²) triangles, even though the complexity of Vₛ(s) can be Ω(n⁴). 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 ₛ∈ ₛ Cₛ(s) that contain p.