Computing a face in an arrangement of line segments

B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, in:, SIAM, 1991, pp. 441–448.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published
Author
; ; ; ;
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.
Publishing Year
Date Published
1991-01-01
Acknowledgement
NSF Grant CC R-89-21421
Page
441 - 448
Conference
SODA: Symposium on Discrete Algorithms
IST-REx-ID

Cite this

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.
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments,” 441–48. SIAM, 1991.
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.
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, et al. Computing a Face in an Arrangement of Line Segments. SIAM, 1991, pp. 441–48.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar