The complexity of many faces in arrangements of lines of segments
Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir · 1988
We show that the total number of edges of m faces of an arrangement of n lines in the plane is Ο(m2/3-δ n2/3+2δ + n), for any δ > 0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of these m faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and, with high probability, its time complexity is within a log2n factor of the above bound. If instead of lines we have an arrangement of n line segments, then the maximum number of edges of m faces is Ogr;(m2/3-δn2/3+2δ + nα(n)logm), for any δ > 0, where α(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and, with high probability, takes time that is within a log2n factor of the combinatorial bound.