Computing a face in an arrangement of line segments and related problems Chazelle, Bernard Edelsbrunner, Herbert ; https://orcid.org/0000-0002-9823-6833 Guibas, Leonidas Sharir, Micha Snoeyink, Jack 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. SIAM 1993 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/4036 Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. Computing a face in an arrangement of line segments and related problems. <i>SIAM Journal on Computing</i>. 1993;22(6):1286-1302. doi:<a href="https://doi.org/10.1137/0222077 ">10.1137/0222077 </a> eng info:eu-repo/semantics/altIdentifier/doi/10.1137/0222077 info:eu-repo/semantics/altIdentifier/issn/0097-5397 info:eu-repo/semantics/closedAccess