Let T be a set of n disjoint triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the visibility map of s with respect to T, i.e., the portions of T that are visible from s. The visibility map of t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n~2) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n~2 log n) upper bound for both structures. Furthermore, we prove that the weak visibility map of s has complexity Θ(n~5), and the weak visibility map of t has complexity Θ(n~7). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n~4) and O(n~5), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.
展开▼
