Arrangement of lines


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. 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.

Definition

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:
  1. The cells or chambers of the arrangement are two-dimensional regions not part of any line. They form the interiors of bounded convex polygons or unbounded convex regions. These are the connected components of the points that would remain after removing all points on lines.
  2. The edges or panels of the arrangement are one-dimensional regions belonging to a single line. They are the open line segments and open infinite rays into which each line is partitioned by its crossing points with the other lines. That is, if one of the lines is cut by all the other lines, these are the connected components of its uncut points.
  3. The vertices of the arrangement are isolated points belonging to two or more lines, where those lines cross each other.
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. 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.

Complexity of arrangements

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:
  • An arrangement with lines has at most vertices, one per pair of crossing lines. This maximum is attained for simple arrangements, those in which each two lines cross at a vertex that is disjoint from all the other lines. The number of vertices is smaller when some lines are parallel, or when some vertices are crossed by more than two lines.
  • An arrangement can be rotated, if necessary, to avoid axis-parallel lines. After this step, each ray that forms an edge of the arrangement extends either upward or downward from its endpoint; it cannot be horizontal. There are downward rays, one per line, and these rays separate cells of the arrangement that are unbounded in the downward direction. The remaining cells all have a unique bottommost vertex. For each pair of lines, there can be only one cell where the two lines meet at the bottom vertex, so the number of downward-bounded cells is at most the number of pairs of Adding the unbounded and bounded cells, the total number of cells in an arrangement can be These are the numbers of the lazy caterer's sequence.
  • The number of edges of the arrangement is 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 edges by the other lines. Simple arrangements have exactly edges.
More complex features go by the names of "zones", "levels", and "many faces":
  • The zone of a in a line arrangement is the collection of cells having edges belonging 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 is and the total number of edges of the cells belonging to both sides is More generally, the total complexity of the cells of a line arrangement that are intersected by any convex curve where denotes the inverse Ackermann function, as may be shown using Davenport–Schinzel sequences. The sum of squares of cell complexities in an arrangement as can be shown by summing the zones of all lines.
  • The of an arrangement is the polygonal chain formed by the edges that have other lines directly below them. The is the portion of the arrangement below the Finding matching upper and lower bounds for the complexity of a remains a major open problem in discrete geometry. The best upper bound known while the best lower bound known In contrast, the maximum complexity of the is known to A 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 there exist arrangements and monotone paths in these arrangements where the number of points at which the path changes direction
  • Although a single cell in an arrangement may be bounded by all lines, it is not possible in general for different cells to all be bounded by lines. Rather, the total complexity of cells is 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 cells have a total of edges, one can form a graph with nodes and edges. 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 crossings in this drawing. However, by the crossing number inequality, there are crossings. In order to satisfy both bounds, must

    Projective arrangements and projective duality

It is convenient to study line arrangements in the projective plane as every pair of lines has a crossing point. 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.
An arrangement of lines in the Euclidean plane can be naturally interpreted as an arrangement of great circles on the 2-sphere. To see this, embed the Euclidean plane as an affine plane not passing through the origin. Every point of determines a line through the origin, which intersects in a pair of antipodal points; likewise, every line in maps to a great circle on the sphere. The equator associated with separates the two hemispheres and plays the role of the line at infinity. Identifying antipodal points on yields the projective plane, where lines in extend naturally to great circles and parallel lines meet at infinity. In this way, the combinatorial structure of line arrangements, including incidences, regions, and intersections, is preserved when transferred to great-circle arrangements on the sphere.
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, uses the Euler characteristic to show that such a vertex must always exist.