@article{4036,
  abstract     = {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.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Snoeyink, Jack},
  issn         = {0097-5397},
  journal      = {SIAM Journal on Computing},
  number       = {6},
  pages        = {1286 -- 1302},
  publisher    = {SIAM},
  title        = {{Computing a face in an arrangement of line segments and related problems}},
  doi          = {10.1137/0222077 },
  volume       = {22},
  year         = {1993},
}