Efficiently Constructing the Visibility Graph of a Simple Polygon with Obstacles
Sanjiv Kapoor, Sachin Maheshwari · SIAM Journal on Computing · 2000
This paper describes an output-sensitive scheme to construct the visibility graph of a simple polygon with m obstacles and n vertices in optimal O(|E| +T + m log n ) time where |E| is the size of the visibility graph and T is the time required to triangulate the simple polygon with obstacles. We use a partition of the space into regions called corridors which eases the efforts of the construction. Our algorithms are simple and the data structures used are only linked lists.