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
N1 - Funding Information:
~rk by Bernard Char,elle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrurmer has been SUP ported by NSF Grant CC R-89-21421. Work by Micha Sharir h-been supported by ONR Grants NOO014-89-J-3042 and NOOOl& 90J-1284, by NSF Grant CCIL89-01484, and by grants from the U.S .-IsraeL Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G .I.F., the German-Israeli Foundation for Scientific Research and Development. t Computer Science Department, t Computer Science Department, Urbana-Champaign
Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.
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 -