Computing a face in an arrangement of line segments and related problems
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1993. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. 22(6), 1286–1302.
Download
No fulltext has been uploaded. References only!
DOI
Journal Article
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Sharir, Micha;
Snoeyink, Jack
;
Guibas, Leonidas;
Sharir, Micha;
Snoeyink, JackAbstract
This paper presents 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 [in Discrete Comput. Geom., 4(1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.
Publishing Year
Date Published
1993-12-01
Journal Title
SIAM Journal on Computing
Acknowledgement
The authors wish to express their gratitude for the generous support and hospitality of the DEC Palo Alto Systems Research Center.
Volume
22
Issue
6
Page
1286 - 1302
ISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. 1993;22(6):1286-1302. doi:10.1137/0222077
Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Snoeyink, J. (1993). Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/0222077
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink. “Computing a Face in an Arrangement of Line Segments and Related Problems.” SIAM Journal on Computing. SIAM, 1993. https://doi.org/10.1137/0222077 .
B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and J. Snoeyink, “Computing a face in an arrangement of line segments and related problems,” SIAM Journal on Computing, vol. 22, no. 6. SIAM, pp. 1286–1302, 1993.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Snoeyink J. 1993. Computing a face in an arrangement of line segments and related problems. SIAM Journal on Computing. 22(6), 1286–1302.
Chazelle, Bernard, et al. “Computing a Face in an Arrangement of Line Segments and Related Problems.” SIAM Journal on Computing, vol. 22, no. 6, SIAM, 1993, pp. 1286–302, doi:10.1137/0222077 .
Google Scholar