Efficient algorithms for computing a complete visibility region in three-dimensional space

Given a set P of polygons in three-dimensional space, two points p and q are said to be visible from each other with respect to P if the line segment joining them does not intersect any polygon in P. A point p is said to be completely visible from an area source S if p is visible from every point in S. The completely visible region CV(S, P) from S with respect to P is defined as the set of all points in three-dimensional space that are completely visible from S. We present two algorithms for computing CV(S, P) for P with a total of n vertices and a convex polygonal source S with m vertices. Our first result is a divide-and-conquer algorithm which runs in O(m(2)n(2) alpha(mn)) time and space, where alpha(mn) is the inverse of Ackermann's function. We next give an incremental algorithm for computing CV(S, P) in O(m(2)n + mn(2) alpha(n)) time and O(mn + n(2)) space. We also prove that CV(S, P) consists of Theta(mn + n(2)) surface elements such as vertices, edges, and faces.