Arrangement of Lines - Complexity of Arrangements

Complexity of Arrangements

The study of arrangements was begun by Jakob Steiner, who proved the first bounds on the maximum number of features of different types that an arrangement may have. An arrangement with n lines has at most n(n − 1)/2 vertices, one per pair of crossing lines. This maximum is achieved for simple arrangements, those in which each two lines has a distinct pair of crossing points. In any arrangement there will be n infinite-downward rays, one per line; these rays separate n + 1 cells of the arrangement that are unbounded in the downward direction. The remaining cells all have a unique bottommost vertex, and each vertex is bottommost for a unique cell, so the number of cells in an arrangement is the number of vertices plus n + 1, or at most n(n + 1)/2 + 1; see lazy caterer's sequence. The number of edges of the arrangement is at most n2, as may be seen either by using the Euler characteristic to calculate it from the numbers of vertices and cells, or by observing that each line is partitioned into at most n edges by the other n − 1 lines; again, this worst-case bound is achieved for simple arrangements.

The zone of a line l in a line arrangement is the collection of cells having edges belonging to l. The zone theorem states that the total number of edges in the cells of a single zone is linear. More precisely, the total number of edges of the cells belonging to a single side of line l is at most 5n − 1, and the total number of edges of the cells belonging to both sides of l is at most . More generally, the total complexity of the cells of a line arrangement that are intersected by any convex curve is O(n α(n)), where α denotes the inverse Ackermann function, as may be shown using Davenport–Schinzel sequences. Summing the complexities of all zones, one finds that the sum of squares of cell complexities in an arrangement is O(n2).

The k-level of an arrangement is the polygonal chain formed by the edges that have exactly k other lines directly below them, and the ≤k-level is the portion of the arrangement below the k-level. Finding matching upper and lower bounds for the complexity of a k-level remains a major open problem in discrete geometry; the best upper bound is O(nk1/3), while the best lower bound is Ω(n exp(c (logk)1/2)). In contrast, the maximum complexity of the ≤k-level is known to be Θ(nk). A k-level is a special case of a monotone path in an arrangement; that is, a sequence of edges that intersects any vertical line in a single point. However, monotone paths may be much more complicated than k-levels: there exist arrangements and monotone paths in these arrangements where the number of points at which the path changes direction is Ω(n2 − o(1)).

Although a single cell in an arrangement may be bounded by all n lines, it is not possible in general for m different cells to all be bounded by n lines. Rather, the total complexity of m cells is at most Θ(m2/3n2/3 + n), almost the same bound as occurs in the Szemerédi–Trotter theorem on point-line incidences in the plane. A simple proof of this follows from the crossing number inequality: if m cells have a total of x + n edges, one can form a graph with m nodes (one per cell) and x edges (one per pair of consecutive cells on the same line). The edges of this graph can be drawn as curves that do not cross within the cells corresponding to their endpoints, and then follow the lines of the arrangement; therefore, there are O(n2) crossings in this drawing. However, by the crossing number inequality, there are Ω(x3/m2) crossings; in order to satisfy both bounds, x must be O(m2/3n2/3).