@inproceedings{4058,
abstract = {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α(n) log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique.},
author = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Snoeyink, Jack},
booktitle = {Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms},
isbn = {978-0-89791-376-8},
location = {San Francisco, CA, United States of America},
pages = {441 -- 448},
publisher = {SIAM},
title = {{Computing a face in an arrangement of line segments}},
year = {1991},
}