We present 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 alpha (n)$ log $n$). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique. We also present 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.

This technical report has been published as

Computing a Face in an Arrangement of Line Segments and Related Problems. Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink, SIAM Journal on Computing, 22(6), 1993, pp. 1286-1302.