Computing a face in an arrangement of line segments and related problems

B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, J. Snoeyink, SIAM Journal on Computing 22 (1993) 1286–1302.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ;
Abstract
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
Volume
22
Issue
6
Page
1286 - 1302
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, 22(6), 1286–1302. 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 22, no. 6 (1993): 1286–1302. 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, 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 .

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar