TY - CONF
AB - 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.
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
AU - Guibas, Leonidas
AU - Sharir, Micha
AU - Snoeyink, Jack
ID - 4058
SN - 978-0-89791-376-8
T2 - Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms
TI - Computing a face in an arrangement of line segments
ER -