The complexity and construction of many faces in arrangements of lines and of segments (Q582900)

The authors show that the number of edges of m faces of an arrangement of n lines in the plane is \(0(m^{2/3-\delta}n^{2/3+2\delta}+n)\) for any \(\delta >0\). This bound is slightly weaker than a tight bound \(\theta (m^{2/3}n^{2/3}+n)\), obtained in another paper by the same authors in a companion paper with K. Clarkson and E. Welzl. The slightly weaker result presented here is a introduction to the more complex case of segments, where the first non-trivial upper bound known for the maximum number of edges of m faces is given. The approach to the combinatorial problem of the paper is also different from previous work in that it has an algorithmic flavor. The algorithm in the case of lines uses randomization and its expected time complexity is \(0(m^{2/3-\delta}n^{2/3+2\delta}\log n+n \log n \log m)\). In the case of line segments an randomized algorithm is also given. The technique used uses \(\epsilon\)-nets and random sampling as basic tools.