Visibility stabs and depth-first spiralling on line segments in output sensitive time

Given a set S of n non-intersecting line segments in the plane, we present a new technique for efficiently traversing the endpoint visibility graph of S to solve a variety of visibility problems in output sensitive time. In p articular, we develop two techniques to compute the 2n visibility polygons of the endpoints of S, in output sensitive time. Depth-first spiralling is a technique that relies on the ordered endpoint visibility graph informatio n to traverse the endpoints of S in a spiral-like manner using a combinatio n of Jarvis' March and depth-first search. It is a practical method and has been implemented in C++ using LEDA.