Visibility maps of segments and triangles in 3D

AbstractLet T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n2) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n2α(n)) upper bound for both structures, where α(n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n5), and the weak visibility map of t has complexity Θ(n7). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n4) and O(n5), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures