THE NUMBER OF EDGES OF MANY FACES IN A LINE SEGMENT ARRANGEMENT

We show that the maximum number of edges bounding m faces in an arrangement of n line segments in the plane is O(m2/3n2/3 + nalpha(n) + n log m). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is OMEGA(m2/3n2/3 + nalpha(n)). In addition, we show that the number of edges bounding any m faces in an arrangement of n line segments with a total of t intersecting pairs is O(m2/3t1/3 + nalpha(t/n) + n min{log m, log t/n}), almost matching the lower bound of OMEGA(m2/3t1/3 + nalpha(t/n)) demonstrated in this paper.