Жазықтықты түзулермен бөлу

Subdivision of the plane by lines

In geometry, an arrangement of lines is the subdivision of the plane formed by a collection of lines. Problems of counting the features of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

Intuitively, any finite set of lines in the plane cuts the plane into two dimensional polygons (cells), one dimensional line segments or rays, and zero dimensional crossing points. This can be formalized mathematically by classifying the points of the plane according to which side of each line they are on. Each line separates the plane into two open half planes, and each point of the plane has three possibilities per line: it can be in either one of these two half planes, or it can be on the line itself. 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 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. If the plane is cut along all of the lines, these are the connected components of the points that remain uncut. 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. 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 (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, in which every bounded subset of the plane may be crossed by only finitely many lines, although in this case the unbounded cells may have infinitely many sides.

It is often convenient to study line arrangements not in the Euclidean plane but in the projective plane, due to the fact that in projective geometry every pair of lines has a crossing point. In the projective plane, it is not possible to define arrangements using sides of lines, because a line in the projective plane does not separate the plane into two distinct sides. However, 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 , uses the Euler characteristic to show that such a vertex must always exist.

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. investigated special cases of this construction in which the line arrangement consists of sets of equally spaced parallel lines. For two perpendicular families of parallel lines this construction just gives the familiar square tiling of the plane, and for three families of lines at 120 degree angles from each other (themselves forming a trihexagonal tiling) this produces the rhombille tiling. However, for more families of lines this construction produces aperiodic tilings. 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. 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 as a doubly connected edge list. Due to the zone theorem, 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 its zone, resulting in a total construction time nowrap|of
As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, such as zones, levels, or the set of cells containing a given set of points. The problem of finding the arrangement vertex with the median coordinate 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.