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
Chazelle, Bernard
;
Edelsbrunner, HerbertIST Austria 
;
Guibas, Leonidas
;
Sharir, Micha
;
Snoeyink, Jack
;
Guibas, Leonidas
;
Sharir, Micha
;
Snoeyink, JackAbstract
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.
Google Scholar