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 algorithm is O(nα (n)log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson–Shor analysis technique [in Discrete Comput. Geom., 4 (1989), pp. 387–421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.