Voronoi-Based Potentially Visible Set and Visibility Query Algorithms

In this paper, we propose the concept of Voronoi based potentially visible set, called V_PVS, to facilitate the visibility computation. Given a polygon P, we first compute the Voronoi diagram of P, i.e., VD(P). Then we refine VD(P) into VD(P´), so that VD(P´) only contains triangular or quadrangular cells. For each Voronoi edge, a V_PVS is computed, which stores the visibility information of the Voronoi vertices and critical points on the edge. Based on the V_PVS, we can fast query the visibility polygons of an arbitrary point, a segment or a trajectory, a region, and a moving point using a uniform data structure.