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
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
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
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.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search