Joachim Gudmundsson
Let S be a set of n disjoint line segments in ℝ2 and let s be an element of S. A well-known example, due to O'Rourke and Suri (1984), shows that the subset, VS(s), of ℝ2 that is weakly visible from s can have complexity Ω(n4). Nevertheless, O'Rourke and Suri show that VS(s) can always be covered by a set CS(s) of O(n2) triangles.
In this paper we revisit the results of Suri and O'Rourke and consider their applications to visibility testing and counting problems. By storing sets of triangles in a version of efficient partition trees (Matousek 1992), we give applications to preprocessing a segment s∈ S so that we can quickly determine if s is visible from a query point p. We also give applications to a visibility counting problem of Fischer et al. (2008) that involves preprocessing S so that one can quickly estimate the number of segments in S visible from a query point p. Some of our latter results rely on a new combinatorial result that relates the number of segments in S visible from a query point to the number of triangles in ∪s∈ S CS(s) that contain p.