TY - JOUR
T1 - Computing a face in an arrangement of line segments and related problems
AU - Chazelle, Bernard
AU - Edelsbrunner, Herbert
AU - Guibas, Leonidas
AU - Sharir, Micha
AU - Snoeyink, Jack
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 1993
Y1 - 1993
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027796404&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027796404&partnerID=8YFLogxK
U2 - 10.1137/0222077
DO - 10.1137/0222077
M3 - Article
AN - SCOPUS:0027796404
SN - 0097-5397
VL - 22
SP - 1286
EP - 1302
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 6
ER -