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, V_{S}(s), of ℝ^{2} that is weakly visible
from s can have complexity Ω(n^{4}). Nevertheless, O'Rourke
and Suri show that V_{S}(s) can always be covered by a set C_{S}(s)
of O(n^{2}) 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} C_{S}(s) that contain p.