conference paper
Computing a face in an arrangement of line segments
published
Bernard
Chazelle
author
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
Leonidas
Guibas
author
Micha
Sharir
author
Jack
Snoeyink
author
SODA: Symposium on Discrete Algorithms
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.
SIAM1991
441 - 448
yes
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1991. Computing a face in an arrangement of line segments. SODA: Symposium on Discrete Algorithms 441–448.
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments,” 441–48. SIAM, 1991.
Chazelle, Bernard, et al. <i>Computing a Face in an Arrangement of Line Segments</i>. SIAM, 1991, pp. 441–48.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing a face in an arrangement of line segments,” presented at the SODA: Symposium on Discrete Algorithms, 1991, pp. 441–448.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, in:, SIAM, 1991, pp. 441–448.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. Computing a face in an arrangement of line segments. In: SIAM; 1991:441-448.
Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Snoeyink, J. (1991). Computing a face in an arrangement of line segments (pp. 441–448). Presented at the SODA: Symposium on Discrete Algorithms, SIAM.
40582018-12-11T12:06:41Z2019-04-26T07:22:39Z