TY - GEN

T1 - Computing a face in an arrangement of line segments

AU - Chazelle, Bernard

AU - Edelsbrunner, Herbert

AU - Guibas, Leonidas

AU - Sharir, Micha

AU - Snoeyink, Jack

PY - 1991/3/1

Y1 - 1991/3/1

N2 - 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 [3].

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 [3].

UR - http://www.scopus.com/inward/record.url?scp=84914756148&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84914756148&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84914756148

SN - 0897913760

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 441

EP - 448

BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

PB - Association for Computing Machinery

T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

Y2 - 28 January 1991 through 30 January 1991

ER -