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 eff orts of the construction. Our algorithms are simple and the data structures used are only linked lists.