In geometry, an arrangement of lines is the subdivision of the Euclidean plane formed by a finite set of lines. An arrangement consists of bounded and unbounded convex polygons, the cells of the arrangement, line segments and rays, the edges of the arrangement, and points where two or more lines cross, the vertices of the arrangement. When considered in the projective plane rather than in the Euclidean plane, every two lines cross, and an arrangement is the projective dual to a finite set of points. Arrangements of lines have also been considered in the hyperbolic plane, and generalized to pseudolines, curves that have similar topological properties to lines. The initial study of arrangements has been attributed to an 1826 paper by Jakob Steiner.
An arrangement is said to be simple when at most two lines cross at each vertex, and simplicial when all cells are triangles (including the unbounded cells, as subsets of the projective plane). There are three known infinite families of simplicial arrangements, as well as many sporadic simplicial arrangements that do not fit into any known family. Arrangements have also been considered for infinite but locally finite systems of lines. Certain infinite arrangements of parallel lines can form simplicial arrangements, and one way of constructing the aperiodic Penrose tiling involves finding the dual graph of an arrangement of lines forming five parallel subsets.
The maximum numbers of cells, edges, and vertices, for arrangements with a given number of lines, are quadratic functions of the number of lines. These maxima are attained by simple arrangements. The complexity of other features of arrangements have been studied in discrete geometry; these include zones, the cells touching a single line, and levels, the polygonal chains having a given number of lines passing below them. Roberts's triangle theorem and the Kobon triangle problem concern the minimum and maximum number of triangular cells in a Euclidean arrangement, respectively.
Algorithms in computational geometry are known for constructing the features of an arrangement in time proportional to the number of features, and space linear in the number of lines. As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, and for problems such as the shortest path problem on the vertices and edges of an arrangement.
As an informal thought experiment, consider cutting an infinite sheet of paper along finitely many lines. These cuts would partition the paper into convex polygons. Their edges would be one-dimensional line segments or rays, with vertices at the points where two cut lines cross. This can be formalized mathematically by classifying the points of the plane according to which side of each line they are on. Each line produces three possibilities per point: the point can be in one of the two open half-planes on either side of the line, or it can be on the line. Two points can be considered to be equivalent if they have the same classification with respect to all of the lines. This is an equivalence relation, whose equivalence classes are subsets of equivalent points. These subsets subdivide the plane into shapes of the following three types:
The boundary of a cell is the system of edges that touch it, and the boundary of an edge is the set of vertices that touch it (one vertex for a ray and two for a line segment). The system of objects of all three types, linked by this boundary operator, form a cell complex covering the plane. Two arrangements are said to be isomorphic or combinatorially equivalent if there is a one-to-one boundary-preserving correspondence between the objects in their associated cell complexes.
The same classification of points, and the same shapes of equivalence classes, can be used for infinite but locally finite arrangements, defined as arrangements in which every bounded subset of the plane is crossed by finitely many lines. In this case the unbounded cells may have infinitely many sides.
It is straightforward to count the maximum numbers of vertices, edges, and cells in an arrangement, all of which are quadratic in the number of lines:
n
n(n-1)/2
n
n+1
n
n-1
n2
More complex features go by the names of "zones", "levels", and "many faces":
\alpha
n
m
n
m
m
x+n
m
x
O(n2)
\Omega(x3/m2)
x
It is convenient to study line arrangements in the projective plane as every pair of lines has a crossing point.[3] Line arrangements cannot be defined using the sides of lines, because a line in the projective plane does not separate the plane into two distinct sides. One may still define the cells of an arrangement to be the connected components of the points not belonging to any line, the edges to be the connected components of sets of points belonging to a single line, and the vertices to be points where two or more lines cross. A line arrangement in the projective plane differs from its Euclidean counterpart in that the two Euclidean rays at either end of a line are replaced by a single edge in the projective plane that connects the leftmost and rightmost vertices on that line, and in that pairs of unbounded Euclidean cells are replaced in the projective plane by single cells that are crossed by the projective line at infinity.
Due to projective duality, many statements about the combinatorial properties of points in the plane may be more easily understood in an equivalent dual form about arrangements of lines. For instance, the Sylvester–Gallai theorem, stating that any non-collinear set of points in the plane has an ordinary line containing exactly two points, transforms under projective duality to the statement that any projective arrangement of finitely many lines with more than one vertex has an ordinary point, a vertex where only two lines cross. The earliest known proof of the Sylvester–Gallai theorem, by Eberhard Melchior in,. plain., uses the Euler characteristic to show that such a vertex must always exist.[4]
An arrangement of lines in the projective plane is said to be simplicial if every cell of the arrangement is bounded by exactly three edges. Simplicial arrangements were first studied by Melchior.[5] Three infinite families of simplicial line arrangements are known:
n-1
Additionally there are many other examples of sporadic simplicial arrangements that do not fit into any known infinite family.[6] As Branko Grünbaum writes, simplicial arrangements "appear as examples or counterexamples in many contexts of combinatorial geometry and its applications." For instance, simplicial arrangements form counterexamples to a conjecture on the relation between the degree of a set of differential equations and the number of invariant lines the equations may have. The two known counterexamples to the Dirac–Motzkin conjecture (which states that any arrangement has at least
n/2
The dual graph of a line arrangement has one node per cell and one edge linking any pair of cells that share an edge of the arrangement. These graphs are partial cubes, graphs in which the nodes can be labeled by bitvectors in such a way that the graph distance equals the Hamming distance between labels. In the case of a line arrangement, each coordinate of the labeling assigns 0 to nodes on one side of one of the lines and 1 to nodes on the other side. Dual graphs of simplicial arrangements have been used to construct infinite families of 3-regular partial cubes, isomorphic to the graphs of simple zonohedra.
It is also of interest to study the extremal numbers of triangular cells in arrangements that may not necessarily be simplicial. Any arrangement in the projective plane must have at least
n
n
n(n-1)/3
n(n-1)/3+4
n\ge4
n\ge6
7n(n-1)/18+1/3
n(n-2)/3
The dual graph of a simple line arrangement may be represented geometrically as a collection of rhombi, one per vertex of the arrangement, with sides perpendicular to the lines that meet at that vertex. These rhombi may be joined together to form a tiling of a convex polygon in the case of an arrangement of finitely many lines, or of the entire plane in the case of a locally finite arrangement with infinitely many lines. This construction is sometimes known as a Klee diagram, after a publication of Rudolf Klee in 1938 that used this technique. Not every rhombus tiling comes from lines in this way, however.[10]
In plain., N. G. de Bruijn investigated special cases of this construction in which the line arrangement consists of
k
There also exist three infinite simplicial arrangements formed from sets of parallel lines. The tetrakis square tiling is an infinite arrangement of lines forming a periodic tiling that resembles a multigrid with four parallel families, but in which two of the families are more widely spaced than the other two, and in which the arrangement is simplicial rather than simple. Its dual is the truncated square tiling. Similarly, the triangular tiling is an infinite simplicial line arrangement with three parallel families, which has as its dual the hexagonal tiling, and the bisected hexagonal tiling is an infinite simplicial line arrangement with six parallel families and two line spacings, dual to the great rhombitrihexagonal tiling. These three examples come from three affine reflection groups in the Euclidean plane, systems of symmetries based on reflection across each line in these arrangements.
Constructing an arrangement means, given as input a list of the lines in the arrangement, computing a representation of the vertices, edges, and cells of the arrangement together with the adjacencies between these objects. For instance, these features may be represented as a doubly connected edge list. Arrangements can be constructed efficiently by an incremental algorithm that adds one line at a time to the arrangement of the previously added lines. Each new line can be added in time proportional to the size of its zone, linear by the zone theorem. This results in a total construction time The memory requirements of this algorithm are also
O(n2)
As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, such as zones,[12] or the set of cells containing a given set of points.[13] The problem of finding the arrangement vertex with the median arises (in a dual form) in robust statistics as the problem of computing the Theil–Sen estimator of a set of points.
Marc van Kreveld suggested the algorithmic problem of computing shortest paths between vertices in a line arrangement, where the paths are restricted to follow the edges of the arrangement, more quickly than the quadratic time that it would take to apply a shortest path algorithm to the whole arrangement graph. An approximation algorithm is known, and the problem may be solved efficiently for lines that fall into a small number of parallel families (as is typical for urban street grids), but the general problem remains open.
A pseudoline arrangement is a family of curves that share similar topological properties with a line arrangement.[14] These can be defined in the projective plane as simple closed curves any two of which meet in a single crossing point.[15] A pseudoline arrangement is said to be stretchable if it is combinatorially equivalent to a line arrangement. Determining stretchability is a difficult computational task: it is complete for the existential theory of the reals to distinguish stretchable arrangements from non-stretchable ones.[16] Every arrangement of finitely many pseudolines can be extended so that they become lines in a "spread", a type of non-Euclidean incidence geometry in which every two points of a topological plane are connected by a unique line (as in the Euclidean plane) but in which other axioms of Euclidean geometry may not apply.
Another type of non-Euclidean geometry is the hyperbolic plane, andarrangements of lines in this geometry have also been studied. Any finite set of lines in the Euclidean plane has a combinatorially equivalent arrangement in the hyperbolic plane (e.g. by enclosing the vertices of the arrangement by a large circle and interpreting the interior of the circle as a Klein model of the hyperbolic plane). However, parallel (non-crossing) pairs of lines are less restricted in hyperbolic line arrangements than in the Euclidean plane: in particular, the relation of being parallel is an equivalence relation for Euclidean lines but not for hyperbolic lines. The intersection graph of the lines in a hyperbolic arrangement can be an arbitrary circle graph. The corresponding concept to hyperbolic line arrangements for pseudolines is a weak pseudoline arrangement,[17] a family of curves having the same topological properties as lines[18] such that any two curves in the family either meet in a single crossing point or have no intersection.[17]
In a survey on arrangements, Pankaj Agarwal and Micha Sharir attribute the study of arrangements to Jakob Steiner, writing that "the first paper on this topic is perhaps" an 1826 paper of Steiner.[19] In this paper, Steiner proved bounds on the maximum number of features of different types that an arrangement may have. After Steiner, the study of arrangements turned to higher-dimensional arrangements of hyperplanes, focusing on their overall structure and on single cells in these arrangements. The study of arrangements of lines, and of more complex features such as zones within these arrangements, returned to interest beginning in the 1980s as part of the foundations of computational geometry.[19]
\tbinom{n}{2}=n(n-1)/2