The spherical visibility map

We introduce a novel representation for visibility in three dimensions and describe an efficient algorithm to construct it. The data structure is a spherical map that consists of a doubly-connected edge list embedded on the surface of a sphere. Each face of the spherical map is labeled with the polygon visible in the corresponding cone. We demonstrate that the algorithm is efficient and robust by presenting the statistics of its time and space requirements for handling several classes of input.