Computing a Face in an Arrangement of Line Segments and Related Problems
Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Jack Scott Snoeyink · SIAM Journal on Computing · 1993
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\alpha (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.