Three-dimensional weak visibility: Complexity and applications

In this paper, we study the complexity of 3D weak visibility. We obtain an O(n(8)) time and Theta(n(6)) space algorithm to compute the weakly visible region of a triangle F from another triangle G among general scenes, which are a set of n disjoint triangles. We also consider the cases when the scenes are rectilinear objects and polyhedral terrains. We show that in these special situations the weakly visible regions can be computed much faster in O(n(6)) time and O(n(4)) space. With these results, we obtain the first known polynomial time algorithm to decide whether or not a simple polyhedron is weakly (internally or externally) visible. (C) 2000 Elsevier Science B.V. All rights reserved.