Computing a face in an arrangement of line segments
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1991. Computing a face in an arrangement of line segments. Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms. SODA: Symposium on Discrete Algorithms, 441–448.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
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
Proceedings Title
Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms
Acknowledgement
NSF Grant CC R-89-21421. The authors wish to express their gratitude for the generous support and hospitality of the DEC Palo Alto Systems Research Center.
Page
441 - 448
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
San Francisco, CA, United States of America
Conference Date
1991-01-28 – 1991-01-30
ISBN
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: Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 1991:441-448.
Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Snoeyink, J. (1991). Computing a face in an arrangement of line segments. In Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms (pp. 441–448). San Francisco, CA, United States of America: SIAM.
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments.” In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, 441–48. SIAM, 1991.
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing a face in an arrangement of line segments,” in Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms, San Francisco, CA, United States of America, 1991, pp. 441–448.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1991. Computing a face in an arrangement of line segments. Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms. SODA: Symposium on Discrete Algorithms, 441–448.
Chazelle, Bernard, et al. “Computing a Face in an Arrangement of Line Segments.” Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1991, pp. 441–48.
Google Scholar
ISBN Search