Efficiently constructing the visibility graph of a simple polygon with obstacles
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.
visibility graph simple polygon obstacles output-sensitive triangulation linked lists