3D Visibility Graph

The visibility graph is a fundamental geometric structure which is useful in many applica- tions, including illumination and rendering, motion planning, pattern recognition, and sensor networks. While the concept of visibility graph is widely studied for 2D scenes, there is not any acceptable equivalence of visibility graph for 3D space. In this paper we explain some reason for this absence. Then we try to ¯nd a new way to de¯ne geometric structure in 3D space. Following our new way, we easily de¯ne a new structure called 3D visibility graph which we believe is the natural way to extend visibility graph in 3D scenes. We show how to compute it in an acceptable time.

Keywords:

computational geometry , visibility graph , 3D visibility