Arrangement of lines

In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

For any set A of lines in the Euclidean plane, one can define an equivalence relation on the points of the plane according to which two points p and q are equivalent if, for every line l of A, either p and q are both on l or both belong to the same open half-plane bounded by l. When A is finite or locally finite the equivalence classes of this relation are of three types:

These three types of objects link together to form a cell complex covering the plane. Two arrangements are said to be isomorphic or combinatorially equivalent if there is a one-to-one adjacency-preserving correspondence between the objects in their associated cell complexes.

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 n², 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.

...
Wikipedia