COMPUTING A FACE IN AN ARRANGEMENT OF LINE SEGMENTS AND RELATED PROBLEMS

This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorith m is O(n alpha(n)log n). The analysis of the algorithm uses a novel ap proach that generalizes and extends the Clarkson-Shor analysis techniq ue [in Discrete Comput.Geom.,4 (1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithm s for constructing the entire arrangement of a collection of line segm ents and for computing a single face in an arrangement of Jordan arcs are also presented.