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 newtechnique for e ciently traversing the endpoint visibility graph of S to solve a variety of
visibility problems in output sensitive time. In particular, we develop two techniques to
compute the 2n visibility polygons of the endpoints of S, in output sensitive time.
Depth- rst spiralling is a technique that relies on the ordered endpoint visibility graph
information to traverse the endpoints of S in a spiral-like manner using a combination of
Jarvis' March and depth- rst search. It is a practical method and has been implemented
in C++ using LEDA.