Arrangement of lines

The initial study of arrangements has been attributed to an 1826 paper by Jakob Steiner.

Arrangements have also been considered for infinite but locally finite systems of lines.

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.

As an informal thought experiment, consider cutting an infinite sheet of paper along finitely many lines.

This can be formalized mathematically by classifying the points of the plane according to which side of each line they are on.

These subsets subdivide the plane into shapes of the following three types:[1] 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.

[1] 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.

[19] 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.

The earliest known proof of the Sylvester–Gallai theorem, by Eberhard Melchior in 1940, uses the Euler characteristic to show that such a vertex must always exist.

[22] As Branko Grünbaum writes, simplicial arrangements "appear as examples or counterexamples in many contexts of combinatorial geometry and its applications.

[27] It is also of interest to study the extremal numbers of triangular cells in arrangements that may not necessarily be simplicial.

[29] The maximum possible number of triangular faces in a simple arrangement is known to be upper bounded by

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.

[33] In a 1981 paper, N. G. de Bruijn investigated special cases of this construction in which the line arrangement consists of

In particular, for five families of lines at equal angles to each other (or, as de Bruijn calls this arrangement, a pentagrid) it produces a family of tilings that include the rhombic version of the Penrose tilings.

[34] 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.

For instance, these features may be represented as a doubly connected edge list.

[36] Computing a line arrangement exactly requires a numerical precision several times greater than that of the input coordinates: if a line is specified by two points on it, the coordinates of the arrangement vertices may need four times as much precision as these input points.

Therefore, computational geometers have also studied algorithms for constructing arrangements with limited numerical precision.

[37] As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, such as zones,[38]

-coordinate arises (in a dual form) in robust statistics as the problem of computing the Theil–Sen estimator of a set of points.

[41] 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.

[42] An approximation algorithm is known,[43] 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),[44] but the general problem remains open.

[46] These can be defined in the projective plane as simple closed curves any two of which meet in a single crossing point.

[48] 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.

The corresponding concept to hyperbolic line arrangements for pseudolines is a weak pseudoline arrangement,[52] a family of curves having the same topological properties as lines[53] such that any two curves in the family either meet in a single crossing point or have no intersection.

[54] In this paper, Steiner proved bounds on the maximum number of features of different types that an arrangement may have.