TY - JOUR
AB - 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.
AU - Chazelle, Bernard
AU - Herbert Edelsbrunner
AU - Guibas, Leonidas
AU - Sharir, Micha
AU - Snoeyink, Jack
ID - 4036
IS - 6
JF - SIAM Journal on Computing
TI - Computing a face in an arrangement of line segments and related problems
VL - 22
ER -