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


Author(s): Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas; Sharir, Micha; Snoeyink, Jack
Article Title: Computing a face in an arrangement of line segments and related problems
Affiliation
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.
Keywords: Algorithms; computational complexity; Random processes
Journal Title: SIAM Journal on Computing
Volume: 22
Issue 6
ISSN: 0097-5397
Publisher: SIAM  
Date Published: 1993-12-01
Start Page: 1286
End Page: 1302
DOI: 10.1137/0222077
Open access: no