View source for Arrangement of lines

{{Short description|Subdivision of the plane by lines}}
{{good article}}
[[File:Complete-quads.svg|thumb|upright=1.35|A simplicial line arrangement (left) and a simple line arrangement (right).]]
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 polygon]]s, the ''cells'' of the arrangement, [[line segment]]s and [[Ray (geometry)|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 [[triangle]]s (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 function]]s 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 [[zone theorem|zones]], the cells touching a single line, and [[K-set (geometry)|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.

[[Algorithm]]s 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 polygon]]s. Their edges would be one-dimensional [[line segment]]s or [[ray (geometry)|rays]], with [[Vertex (geometry)|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-plane]]s 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 class]]es are subsets of equivalent points. These subsets subdivide the plane into shapes of the following three types:{{sfnp|Grünbaum|1972|p=4}}
#The ''cells'' or ''chambers'' of the arrangement are two-dimensional regions not part of any line. They form the interiors of bounded [[convex polygon]]s or unbounded convex regions. These are the [[Connected component (topology)|connected components]] of the points that would remain after removing all points on lines.{{sfnp|Grünbaum|1972|p=4}}
#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.{{sfnp|Grünbaum|1972|p=4}}
#The ''[[vertex (geometry)|vertices]]'' of the arrangement are isolated points belonging to two or more lines, where those lines cross each other.{{sfnp|Grünbaum|1972|p=4}}
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.{{sfnp|Grünbaum|1972|p=4}}

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.{{sfnp|Eppstein|Falmagne|Ovchinnikov|2007|pp=177–178}} In this case the unbounded cells may have infinitely many sides.{{sfnp|Ovchinnikov|2011|p=210}}

==Complexity of arrangements==
It is straightforward to count the maximum numbers of vertices, edges, and cells in an arrangement, all of which are [[quadratic growth|quadratic]] in the number of lines:
*An arrangement with <math>n</math> lines has at most <math>n(n-1)/2</math> vertices (a [[triangular number]]), 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.<ref>{{harvtxt|Halperin|Sharir|2018|p=[https://books.google.com/books?id=9mlQDwAAQBAJ&pg=PA724 724]}}. This source gives a formula for the number of cells of variable dimension in a [[hyperplane arrangement]] of variable dimension, which simplifies to <math>\tbinom{n}{2}=n(n-1)/2</math> in the case of vertices (cells of dimension 0) in an arrangement of dimension 2.</ref>
*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 <math>n</math> downward rays, one per line, and these rays separate <math>n+1</math> cells of the arrangement that are unbounded in the downward direction. The remaining cells all have a unique bottommost vertex (again, because there are no axis-parallel lines). 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 {{nowrap|lines, <math>n(n-1)/2</math>.}} Adding the unbounded and bounded cells, the total number of cells in an arrangement can be {{nowrap|at most <math>n(n+1)/2+1</math>.{{sfnp|Halperin|Sharir|2018|p=[https://books.google.com/books?id=9mlQDwAAQBAJ&pg=PA724 724]}}}} These are the numbers of the [[lazy caterer's sequence]].{{sfnp|Sloane}}
*The number of edges of the arrangement is {{nowrap|at most <math>n^2</math>,}} 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 <math>n</math> edges by the other <math>n-1</math> lines. Simple arrangements have exactly <math>n^2</math> edges.{{sfnp|Halperin|Sharir|2018|p=[https://books.google.com/books?id=9mlQDwAAQBAJ&pg=PA724 724]}}

More complex features go by the names of "zones", "levels", and "many faces":
{{anchor|Zone theorem}}
*The ''zone'' of a {{nowrap|line <math>\ell</math>}} in a line arrangement is the collection of cells having edges belonging {{nowrap|to <math>\ell</math>.}} 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 {{nowrap|line <math>\ell</math>}} is {{nowrap|at most <math>5n-1</math>,<ref name="zone">{{harvtxt|Chazelle|Guibas|Lee|1985|at=Lemma 1|p=80}}, {{harvtxt|Edelsbrunner|1987|at=Section 5.3, Zones in arrangements: tight bounds in the plane|pp=89–92}}, {{harvtxt|Edelsbrunner|O'Rourke|Seidel|1986|at=Theorem 2.7|p=346}}.</ref>}} and the total number of edges of the cells belonging to both sides {{nowrap|of <math>\ell</math>}} is {{nowrap|at most <math>\lfloor 9.5n\rfloor-1</math>.<ref>{{harvtxt|Bern|Eppstein|Plassman|Yao|1991}}; an unpublished manuscript of Rom Pinchasi from 2011 claims the slightly stronger bound <math>\lfloor 9.5n\rfloor-3</math>.</ref>}} More generally, the total complexity of the cells of a line arrangement that are intersected by any [[convex curve]] {{nowrap|is <math>O(n\alpha(n))</math>,}} where <math>\alpha</math> denotes the [[Ackermann function|inverse Ackermann function]], as may be shown using [[Davenport–Schinzel sequence]]s.{{sfnp|Bern|Eppstein|Plassman|Yao|1991}} The sum of squares of cell complexities in an arrangement {{nowrap|is <math>O(n^2)</math>,}} as can be shown by summing the zones of all lines.{{sfnp|Aronov|Matoušek|Sharir|1994}}
*The {{nowrap|<math>k</math>-''[[K-set (geometry)|level]]''}} of an arrangement is the [[polygonal chain]] formed by the edges that have {{nowrap|exactly <math>k</math>}} other lines directly below them. The {{nowrap|<math>\le k</math>-level}} is the portion of the arrangement below the {{nowrap|<math>k</math>-level.}} Finding matching upper and lower bounds for the complexity of a {{nowrap|<math>k</math>-level}} remains a major open problem in discrete geometry. The best upper bound known {{nowrap|is <math>O(nk^{1/3})</math>,}} while the best lower bound known {{nowrap|is <math>n2^{\Omega(\sqrt{\log k})}</math>.<ref>{{harvtxt|Dey|1998}}; {{harvtxt|Tóth|2001}}. The problem of bounding the complexity of ''k''-levels was first studied by {{harvtxt|Lovász|1971}} and {{harvtxt|Erdős|Lovász|Simmons|Straus|1973}}.</ref>}} In contrast, the maximum complexity of the {{nowrap|<math>\le k</math>-level}} is known to {{nowrap|be <math>\Theta(nk)</math>.{{sfnp|Alon|Győri|1986}}}} A {{nowrap|<math>k</math>-level}} 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 {{nowrap|<math>k</math>-levels:}} there exist arrangements and monotone paths in these arrangements where the number of points at which the path changes direction {{nowrap|is <math>n^{2-o(1)}</math>.<ref>{{harvtxt|Balogh|Regev|Smyth|Steiger|2004}}; see also {{harvtxt|Matoušek|1991}}.</ref>}}
*Although a single cell in an arrangement may be bounded by all <math>n</math> lines, it is not possible in general for <math>m</math> different cells to all be bounded by <math>n</math> lines. Rather, the total complexity of <math>m</math> cells is {{nowrap|at most <math>\Theta(m^{2/3}n^{2/3}+n)</math>,<ref>{{harvtxt|Canham|1969}}; {{harvtxt|Clarkson|Edelsbrunner|Guibas|Sharir|1990}}.</ref>}} almost the same bound as occurs in the [[Szemerédi–Trotter theorem]] on point-line [[Incidence (geometry)|incidences]] in the plane. A simple proof of this follows from the [[Crossing number (graph theory)|crossing number inequality]]:<ref>{{harvtxt|Ajtai|Chvátal|Newborn|Szemerédi|1982}}; {{harvtxt|Leighton|1983}}.</ref> if <math>m</math> cells have a total of <math>x+n</math> edges, one can form a graph with <math>m</math> nodes (one per cell) and <math>x</math> edges (one per pair of consecutive cells on the same line). 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 <math>O(n^2)</math> crossings in this drawing. However, by the crossing number inequality, there are <math>\Omega(x^3/m^2)</math> crossings. In order to satisfy both bounds, <math>x</math> must {{nowrap|be <math>O(m^{2/3}n^{2/3})</math>.{{sfnp|Székely|1997}}}}

==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.<ref>{{harvtxt|Goodman|Pollack|1993}}, [https://books.google.com/books?id=lGbvCAAAQBAJ&pg=PA109 p. 109] {{Webarchive|url=https://web.archive.org/web/20230101072017/https://books.google.com/books?id=lGbvCAAAQBAJ&pg=PA109 |date=2023-01-01 }}: "The natural setting for arrangements of lines is the real projective plane"</ref> 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.{{sfnp|Polster|1998|p=223}} 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.{{sfnp|Goodman|Pollack|1993|p=110}}

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 {{citeref|Melchior|1940|1940|style=plain}}, uses the [[Euler characteristic]] to show that such a vertex must always exist.<ref>This is the earliest proof cited by {{harvtxt|Borwein|Moser|1990|pp=114–116}}, but they write that the same proof was likely given "much earlier by others" (p. 114).</ref>

==Triangles in arrangements==
[[File:Decagon simplicial arrangement.svg|thumb|A simplicial arrangement formed by 20 lines, the sides and symmetry axes of a regular [[decagon]]. Adding the [[line at infinity]] produces another simplicial arrangement with 21 lines.]]
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.<ref>{{harvtxt|Melchior|1940}}; {{harvtxt|Grünbaum|2009|p=1}}.</ref> Three infinite families of simplicial line arrangements are known:
#A ''near-pencil'' consisting of <math>n-1</math> lines through a single point, together with a single additional line that does not go through the same point,
#The family of lines formed by the sides of a [[regular polygon]] together with its [[axis of symmetry|axes of symmetry]], and
#The sides and axes of symmetry of an even regular polygon, together with the line at infinity.
Additionally there are many other examples of ''sporadic simplicial arrangements'' that do not fit into any known infinite family.<ref>{{harvtxt|Grünbaum|2009}}; {{harvtxt|Cuntz|2022}}.</ref>
As [[Branko Grünbaum]] writes, simplicial arrangements "appear as examples or counterexamples in many contexts of combinatorial geometry and its applications."{{sfnp|Grünbaum|2009|p=4}} For instance, simplicial arrangements form counterexamples to a conjecture on the relation between the degree of a set of [[differential equation]]s and the number of invariant lines the equations may have.{{sfnp|Artés|Grünbaum|Llibre|1998}} The two known counterexamples to the [[Dirac–Motzkin conjecture]] (which states that any {{nowrap|<math>n</math>-line}} arrangement has at least <math>n/2</math> ordinary points) are both simplicial.<ref>{{harvtxt|Crowe|McKee|1968}}; {{harvtxt|Dirac|1951}}; {{harvtxt|Kelly|Moser|1958}}; {{harvtxt|Grünbaum|1972|p=18}}.</ref>

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 cube]]s, graphs in which the nodes can be labeled by [[bitvector]]s 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.{{sfnp|Eppstein|Falmagne|Ovchinnikov|2007|p=180}} Dual graphs of simplicial arrangements have been used to construct infinite families of [[cubic graph|3-regular]] partial cubes, isomorphic to the graphs of [[zonohedron|simple zonohedra]].{{sfnp|Eppstein|2006}}

{{multiple image
|image1=Roberts triangle theorem n=7.svg|caption1=An arrangement with the minimum number of triangles according to [[Roberts's triangle theorem]]
|image2=17KobonDreiecke.svg||caption2=[[Kobon triangle problem|Kobon triangles]] in an arrangement of 17 lines
|total_width=480}}
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 <math>n</math> triangles. Every arrangement that has only <math>n</math> triangles must be simple.<ref>{{harvtxt|Grünbaum|1972|at=Theorem 2.20 and Conjecture 2.7|p=25}}; {{harvtxt|Levi|1926}}; {{harvtxt|Roudneff|1988}}.</ref> For Euclidean rather than projective arrangements, the minimum number of triangles {{nowrap|is <math>n-2</math>,}} by [[Roberts's triangle theorem]].{{sfnp|Grünbaum|1998}} The maximum possible number of triangular faces in a simple arrangement is known to be upper bounded by <math>n(n-1)/3</math> and lower bounded {{nowrap|by <math>n(n-3)/3</math>;}} the lower bound is achieved by certain subsets of the diagonals of a regular {{nowrap|<math>2n</math>-gon.<ref>{{harvtxt|Füredi|Palásti|1984}}; {{harvtxt|Grünbaum|1972|pp=26-30}}.</ref>}} For projective arrangements that are not required to be simple, there exist arrangements with <math>n(n-1)/3+4</math> triangles for all <math>n\ge 4</math>, and all arrangements with <math>n\ge 6</math> have at most <math>7n(n-1)/18+1/3</math> triangles.<ref>{{harvtxt|Purdy|1979}}; {{harvtxt|Purdy|1980}}; {{harvtxt|Strommer|1977}}.</ref> The closely related [[Kobon triangle problem]] asks for the maximum number of non-overlapping finite triangles in an arrangement in the Euclidean plane, not counting the unbounded faces that might form triangles in the projective plane. Again, the arrangements are not required to be simple. For some but not all values {{nowrap|of <math>n</math>,}} there exist arrangements with <math>n(n-2)/3</math> triangles.{{sfnp|Moreno|Prieto-Martínez|2021}}

==Multigrids and rhombus tilings==
The dual graph of a simple line arrangement may be represented geometrically as a collection of [[rhombus|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.<ref>{{harvtxt|Klee|1938}}, as cited by {{harvtxt|Grünbaum|1974|p=101}}.</ref>

In {{citeref|de Bruijn|1981|a 1981 paper|style=plain}}, [[Nicolaas Govert de Bruijn|N. G. de Bruijn]] investigated special cases of this construction in which the line arrangement consists of <math>k</math> sets of equally spaced parallel lines. For two perpendicular families of parallel lines this construction gives the [[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 tiling]]s. 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 tiling]]s.{{sfnp|de Bruijn|1981}}

{{multiple image
|image1=Tiling Dual Semiregular V4-8-8 Tetrakis Square.svg|caption1=[[Tetrakis square tiling]]
|image2=Tiling Regular 3-6 Triangular.svg|caption2=[[Triangular tiling]]
|image3=Tiling Dual Semiregular V4-6-12 Bisected Hexagonal.svg|caption3=[[Bisected hexagonal tiling]]
|total_width=600}}
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 [[Reflection group|affine reflection group]]s in the Euclidean plane, systems of symmetries based on reflection across each line in these arrangements.{{sfnp|Abramenko|Brown|2008|at=Example 10.14|pp=519–520}}

==Algorithms==
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 {{nowrap|of <math>O(n^2)</math>.<ref name="zone"/>}} The memory requirements of this algorithm are also <math>O(n^2)</math>. It is possible instead to report the features of an arrangement without storing them all at once, in {{nowrap|time <math>O(n^2)</math>}} and {{nowrap|space <math>O(n)</math>,}} by an [[algorithmic technique]] known as topological sweeping.{{sfnp|Edelsbrunner|Guibas|1989}} 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.<ref>{{harvtxt|Fortune|Milenkovic|1991}}; {{harvtxt|Greene|Yao|1986}}; {{harvtxt|Milenkovic|1989}}.</ref>

As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, such as zones,<ref>{{harvtxt|Aharoni|Halperin|Hanniel|Har-Peled|1999}}; {{harvtxt|Wang|2022a}}.</ref> {{nowrap|<math>k</math>-levels,<ref>{{harvtxt|Agarwal|de Berg|Matoušek|Schwarzkopf|1998}}; {{harvtxt|Chan|1999}}; {{harvtxt|Cole|Sharir|Yap|1987}}; {{harvtxt|Edelsbrunner|Welzl|1986}}; {{harvtxt|Halperin|Har-Peled|Mehlhorn|Oh|2022}}.</ref>}} or the set of cells containing a given set of points.<ref>{{harvtxt|Agarwal|1990}}; {{harvtxt|Agarwal|Matoušek|Sharir|1998}}; {{harvtxt|Edelsbrunner|Guibas|Sharir|1990}}; {{harvtxt|Wang|2022b}}.</ref> The problem of finding the arrangement vertex with the median {{nowrap|<math>x</math>-coordinate}} arises (in a dual form) in [[robust statistics]] as the problem of computing the [[Theil–Sen estimator]] of a set of points.{{sfnp|Cole|Salowe|Steiger|Szemerédi|1989}}

Marc van Kreveld suggested the algorithmic problem of computing [[shortest path]]s 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.{{sfnp|Erickson|1997}} An [[approximation algorithm]] is known,{{sfnp|Bose|Evans|Kirkpatrick|McAllister|1996}} 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),{{sfnp|Eppstein|Hart|1999}} but the general problem remains open.{{sfnp|Likhtarov|2020}}

==Non-Euclidean line arrangements==
{{multiple images
<!-- Essential parameters -->
| align     = center
| direction = horizontal
| image1    = Pappos_pseudo.svg
| width1    = 383
| caption1  = A non-stretchable pseudoline arrangement of nine pseudolines. (All arrangements of fewer than nine pseudolines are stretchable.) Per [[Pappus's hexagon theorem]], this arrangement cannot be realized in a [[projective plane]] over any field.

| image2    = Ageev 5X circle graph.svg
| width2    = 300
| caption2  = A hyperbolic line arrangement combinatorially equivalent to a [[Chord diagram (mathematics)|chord diagram]] used by {{harvtxt|Ageev|1996}} to show that [[triangle-free graph|triangle-free]] [[circle graph]]s may sometimes need [[graph coloring|5 colors]].
}}

A '''pseudoline arrangement''' is a family of [[curve]]s that share similar [[topology|topological]] properties with a line arrangement.<ref>{{harvtxt|Grünbaum|1972|p=40}}; {{harvtxt|Agarwal|Sharir|2002}}.</ref> These can be defined in the [[projective plane]] as [[simple closed curve]]s any two of which meet in a single crossing point.<ref>This definition is from {{harvtxt|Grünbaum|1972|p=40}}. For a comparison of alternative definitions of pseudolines, see {{harvtxt|Eppstein|Falmagne|Ovchinnikov|2007|pp=238–239}}.</ref> 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 (complexity)|complete]] for the [[existential theory of the reals]] to distinguish stretchable arrangements from non-stretchable ones.<ref>{{harvtxt|Shor|1991}}; {{harvtxt|Schaefer|2010|p=334}}.</ref> 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.{{sfnp|Goodman|Pollack|Wenger|Zamfirescu|1994}}

Another type of non-Euclidean geometry is the [[Hyperbolic space|hyperbolic plane]], and
arrangements of lines in this geometry have also been studied.{{sfnp|Dress|Koolen|Moulton|2002}} 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.{{sfnp|Martin|1996|pages=41, 338}} 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'',<ref name=wpla>{{harvtxt|de Fraysseix|Ossona de Mendez|2003}}.</ref> a family of curves having the same topological properties as lines<ref>Here an alternative definition from {{harvtxt|Shor|1991}}, that a pseudoline is the image of a line under a [[homeomorphism]] of the plane, is appropriate.</ref> such that any two curves in the family either meet in a single crossing point or have no intersection.<ref name=wpla/>

==History==
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.<ref name=as00>{{harvtxt|Agarwal|Sharir|2000|page=52}} (page 2 of preprint version).</ref> In this paper, Steiner proved bounds on the maximum number of features of different types that an arrangement may have.{{sfnp|Steiner|1826}} After Steiner, the study of arrangements turned to higher-dimensional [[Arrangement of hyperplanes|arrangements of hyperplane]]s, 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]].<ref name=as00/>

==See also==
*[[Configuration (geometry)]], an arrangement of lines and a set of points with all lines containing the same number of points and all points belonging to the same number of lines
*[[Arrangement (space partition)]], a partition of the plane given by overlaid curves or of a higher dimensional space by overlaid surfaces, without requiring the curves or surfaces to be flat
*[[Mathematical Bridge]], a bridge in Cambridge, England whose beams form an arrangement of tangent lines to its arch

==Notes==
{{reflist|25em}}

==References==
{{refbegin|30em}}
*{{citation
 | last1 = Abramenko | first1 = Peter
 | last2 = Brown | first2 = Kenneth S.
 | doi = 10.1007/978-0-387-78835-7
 | isbn = 978-0-387-78834-0
 | mr = 2439729
 | publisher = Springer | location = New York
 | series = Graduate Texts in Mathematics
 | title = Buildings: Theory and Applications
 | volume = 248
 | year = 2008}}
*{{citation
 | last = Agarwal | first = P. K. | authorlink = Pankaj K. Agarwal
 | doi = 10.1007/BF02187809
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | pages = 533–573
 | title =  Partitioning arrangements of lines II: Applications
 | volume = 5
 | year = 1990| doi-access = free
 }}
*{{citation
 | last1 = Agarwal | first1 = P. K. | author1-link = Pankaj K. Agarwal
 | last2 = de Berg | first2 = M. | author2-link = Mark de Berg
 | last3 = Matoušek | first3 = J. | author3-link = Jiří Matoušek (mathematician)
 | last4 = Schwarzkopf | first4 = O. | author4-link = Otfried Cheong
 | doi = 10.1137/S0097539795281840
 | issue = 3
 | journal = [[SIAM Journal on Computing]]
 | pages = 654–667
 | title = Constructing levels in arrangements and higher order Voronoi diagrams
 | volume = 27
 | year = 1998| citeseerx = 10.1.1.51.5064 }}
*{{citation
 | last1 = Agarwal | first1 = P. K. | author1-link = Pankaj K. Agarwal
 | last2 = Matoušek | first2 = J. | author2-link = Jiří Matoušek (mathematician)
 | last3 = Sharir | first3 = M. | author3-link = Micha Sharir
 | doi = 10.1137/S009753979426616X
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | pages = 491–505
 | title = Computing many faces in arrangements of lines and segments
 | volume = 27
 | year = 1998| hdl = 1874/17088 | hdl-access = free
 }}
*{{citation
 |last1            = Agarwal
 |first1           = P. K.
 |author1-link     = Pankaj K. Agarwal
 |last2            = Sharir
 |first2           = M.
 |author2-link     = Micha Sharir
 |contribution     = Arrangements and their applications
 |editor1-last     = Sack
 |editor1-first    = J.-R.
 |editor1-link     = Jörg-Rüdiger Sack
 |editor2-last     = Urrutia
 |editor2-first    = J.
 |editor2-link     = Jorge Urrutia Galicia
 |pages            = 49–119
 |publisher        = Elsevier
 |title            = Handbook of Computational Geometry
 |contribution-url = https://users.cs.duke.edu/~pankaj/publications/surveys/arrangement-survey.pdf
 |year             = 2000
 |access-date      = 2024-10-16
 |archive-date     = 2021-04-11
 |archive-url      = https://web.archive.org/web/20210411195507/https://users.cs.duke.edu/~pankaj/publications/surveys/arrangement-survey.pdf
 |url-status       = live
}}
*{{citation
 | last1 = Agarwal
 | first1 = P. K.
 | author1-link = Pankaj K. Agarwal
 | last2 = Sharir
 | first2 = M.
 | author2-link = Micha Sharir
 | contribution = Pseudo-line arrangements: duality, algorithms, and applications
 | location = San Francisco
 | pages = 800–809
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02)
 | contribution-url = http://portal.acm.org/citation.cfm?id=545486
 | year = 2002
 | title-link = Symposium on Discrete Algorithms
 }}
*{{citation
 | doi = 10.1016/0012-365X(95)00349-2
 | last = Ageev | first = A. A.
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 295–298
 | title = A triangle-free circle graph with chromatic number 5
 | volume = 152
 | issue = 1–3 | year = 1996| doi-access = free
 }}
*{{citation
 | last1 = Aharoni
 | first1 = Y.
 | last2 = Halperin
 | first2 = D.
 | last3 = Hanniel
 | first3 = I.
 | last4 = Har-Peled
 | first4 = S.
 | author4-link = Sariel Har-Peled
 | last5 = Linhart
 | first5 = C.
 | contribution = On-line zone construction in arrangements of lines in the plane
 | doi = 10.1007/3-540-48318-7_13
 | pages = [https://archive.org/details/algorithmenginee0000inte/page/139 139–153]
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Algorithm Engineering: 3rd International Workshop, WAE'99, London, UK, July 19–21, 1999, Proceedings
 | editor1-first = Jeffrey S.
 | editor1-last = Vitter
 | editor1-link = Jeffrey Vitter
 | editor2-first = Christos D.
 | editor2-last = Zaroliagis
 | volume = 1668
 | year = 1999
 | isbn = 978-3-540-66427-7
 | citeseerx = 10.1.1.35.7681
 }}
*{{citation
 | last1 = Ajtai | first1 = M. | author1-link = Miklós Ajtai
 | last2 = Chvátal | first2 = V. | author2-link = Václav Chvátal
 | last3 = Newborn | first3 = M. | author3-link = Monty Newborn
 | last4 = Szemerédi | first4 = E. | author4-link = Endre Szemerédi
 | contribution = Crossing-free subgraphs
 | pages = 9–12
 | series = North-Holland Mathematics Studies
 | volume = 60
 | publisher = North-Holland
 | title = Theory and Practice of Combinatorics
 | year = 1982
 | mr = 806962}}
*{{citation
 | last1 = Alon | first1 = N. | author1-link = Noga Alon
 | last2 = Győri | first2 = E.
 | doi = 10.1016/0097-3165(86)90122-6
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 154–157
 | title = The number of small semi-spaces of a finite set of points in the plane
 | volume = 41
 | year = 1986| doi-access = free
 }}
*{{citation
 | last1 = Aronov | first1 = B. | author1-link = Boris Aronov
 | last2 = Matoušek | first2 = J. | author2-link = Jiří Matoušek (mathematician)
 | last3 = Sharir | first3 = M. | author3-link = Micha Sharir
 | doi = 10.1016/0097-3165(94)90027-2
 | issue = 2
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 311–321
 | title = On the sum of squares of cell complexities in hyperplane arrangements
 | volume = 65
 | year = 1994| doi-access = free
 }}
*{{citation
 | doi = 10.2140/pjm.1998.184.207
 | last1 = Artés
 | first1 = J. C.
 | last2 = Grünbaum
 | first2 = B.
 | author2-link = Branko Grünbaum
 | last3 = Llibre
 | first3 = J.
 | issue = 2
 | journal = [[Pacific Journal of Mathematics]]
 | pages = 207–230
 | title = On the number of invariant straight lines for polynomial differential systems
 | url = http://pjm.math.berkeley.edu/pjm/1998/184-2/pjm-v184-n2-p02-p.pdf
 | volume = 184
 | year = 1998
 | doi-access = free
 | access-date = 2008-12-15
 | archive-date = 2010-07-18
 | archive-url = https://web.archive.org/web/20100718184147/http://pjm.math.berkeley.edu/pjm/1998/184-2/pjm-v184-n2-p02-p.pdf
 | url-status = dead
 }}
*{{citation
 | last1 = Balogh | first1 = J.
 | last2 = Regev | first2 = O.
 | last3 = Smyth | first3 = C.
 | last4 = Steiger | first4 = W.
 | last5 = Szegedy | first5 = M. | author5-link = Mario Szegedy
 | doi = 10.1007/s00454-004-1119-1
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | pages = 167–176
 | title = Long monotone paths in line arrangements
 | volume = 32
 | year = 2004| doi-access = free
 }}
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Eppstein | first2 = D. | author2-link = David Eppstein
 | last3 = Plassman | first3 = P. E.
 | last4 = Yao | first4 = F. F. | author4-link = Frances Yao
 | contribution = Horizon theorems for lines and polygons
 | edition = 6
 | editor1-last = Goodman | editor1-first = J. E. | editor1-link = Jacob E. Goodman
 | editor2-last = Pollack | editor2-first = R. | editor3-link = Richard M. Pollack
 | editor3-last = Steiger | editor3-first = W.
 | pages = 45–66
 | publisher = Amer. Math. Soc.
 | series = DIMACS Ser. Discrete Math. and Theoretical Computer Science
 | title = Discrete and Computational Geometry: Papers from the DIMACS Special Year
 | year = 1991
 | mr =1143288 }}
*{{citation | last1 = Borwein | first1 = P. | author1-link = Peter Borwein | last2 = Moser | first2 = W. O. J.| title = A survey of Sylvester's problem and its generalizations| journal = [[Aequationes Mathematicae]] | volume = 40 | issue = 1 | year = 1990 | doi = 10.1007/BF02112289 | pages = 111–135|mr=1069788| s2cid = 122052678 }}
*{{citation
 | last1 = Bose | first1 = P. | author1-link = Jit Bose
 | last2 = Evans | first2 = W.
 | last3 = Kirkpatrick | first3 = D. G. | author3-link = David G. Kirkpatrick
 | last4 = McAllister | first4 = M.
 | last5 = Snoeyink | first5 = J.
 | contribution = Approximating shortest paths in arrangements of lines
 | pages = 143–148
 | title = Proc. 8th Canadian Conf. Computational Geometry
 | year = 1996}}
*{{citation
 | last = de Bruijn
 | first = N. G.
 | author-link = Nicolaas Govert de Bruijn
 | journal = [[Indagationes Mathematicae]]
 | pages = 38–66
 | title = Algebraic theory of Penrose's non-periodic tilings of the plane
 | url = http://alexandria.tue.nl/repository/freearticles/597566.pdf
 | volume = 43
 | year = 1981
 | access-date = 2024-10-16
 | archive-date = 2021-05-07
 | archive-url = https://web.archive.org/web/20210507002645/https://alexandria.tue.nl/repository/freearticles/597566.pdf
 | url-status = live
 }}
*{{citation
 | doi = 10.1007/BF02788872 | doi-access=free
 | last = Canham | first = R. J.
 | journal = [[Israel Journal of Mathematics]]
 | pages = 393–397
 | title = A theorem on arrangements of lines in the plane
 | volume = 7
 | year = 1969
 | issue = 4| s2cid = 123541779 }}
*{{citation 
 |last=Chan 
 |first=T. 
 |author-link=Timothy M. Chan 
 |title=Remarks on {{mvar|k}}-level algorithms in the plane 
 |url=http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz 
 |year=1999 
 |url-status=dead 
 |archiveurl=https://web.archive.org/web/20101104182509/http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz 
 |archivedate=2010-11-04 
 }}
*{{citation
 | last1 = Chazelle | first1 = B. | author1-link = Bernard Chazelle
 | last2 = Guibas | first2 = L. J. | author2-link = Leonidas J. Guibas
 | last3 = Lee | first3 = D. T. | author3-link = Der-Tsai Lee
 | doi = 10.1007/BF01934990
 | issue = 1
 | journal = [[BIT Numerical Mathematics]]
 | pages = 76–90
 | title = The power of geometric duality
 | volume = 25
 | year = 1985| s2cid = 122411548 }}
*{{citation
 | last1 = Clarkson | first1 = K. | author1-link = Kenneth L. Clarkson
 | last2 = Edelsbrunner | first2 = H. | author2-link = Herbert Edelsbrunner
 | last3 = Guibas | first3 = L. J. | author3-link = Leonidas J. Guibas
 | last4 = Sharir | first4 = M. | author4-link = Micha Sharir
 | last5 = Welzl | first5 = E. | author5-link = Emo Welzl
 | doi = 10.1007/BF02187783
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | pages = 99–160
 | title = Combinatorial complexity bounds for arrangements of curves and spheres
 | volume = 5
 | year = 1990| doi-access = free}}
*{{citation
 | last1 = Cole | first1 = Richard
 | last2 = Salowe | first2 = Jeffrey S.
 | last3 = Steiger | first3 = W. L.
 | last4 = Szemerédi | first4 = Endre | author4-link = Endre Szemerédi
 | doi = 10.1137/0218055
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 1004799
 | pages = 792–810
 | title = An optimal-time algorithm for slope selection
 | volume = 18
 | year = 1989}}
*{{citation
 | last1 = Cole | first1 = R.
 | last2 = Sharir | first2 = M. | author2-link = Micha Sharir
 | last3 = Yap | first3 = C.-K.
 | doi = 10.1137/0216005
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | pages = 61–77
 | title = On {{mvar|k}}-hulls and related problems
 | volume = 16
 | year = 1987}}
*{{citation
 | doi = 10.2307/2687957
 | last1 = Crowe | first1 = D. W.
 | last2 = McKee | first2 = T. A.
 | issue = 1
 | journal = [[Mathematics Magazine]]
 | pages = 30–34
 | title = Sylvester's problem on collinear points
 | volume = 41
 | year = 1968
 | jstor = 2687957}}
*{{citation
 | last = Cuntz | first = Michael
 | doi = 10.1007/s00454-021-00351-y
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | mr = 4430282
 | pages = 107–124
 | title = A greedy algorithm to compute arrangements of lines in the projective plane
 | volume = 68
 | year = 2022| doi-access = free
 | arxiv = 2006.14431
 }}
*{{citation
 | last = Dey | first = T. L.
 | doi = 10.1007/PL00009354
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | pages = 373–382
 | title = Improved bounds for planar {{mvar|k}}-sets and related problems
 | volume = 19
 | year = 1998
 | mr = 1608878| doi-access = free
 }}
*{{citation
 | last = Dirac | first = G. | author-link = Gabriel Andrew Dirac
 | doi = 10.1093/qmath/2.1.221
 | journal = [[Quarterly Journal of Mathematics]]
 | pages = 221–227
 | title = Collinearity properties of sets of points
 | volume = 2
 | issue = 1 | year = 1951| bibcode = 1951QJMat...2..221D}}
*{{citation
 | last1 = Dress | first1 = A.
 | last2 = Koolen | first2 = J. H.
 | last3 = Moulton | first3 = V.
 | doi = 10.1006/eujc.2002.0582
 | issue = 5
 | journal = European Journal of Combinatorics
 | mr = 1931939
 | pages = 549–557
 | title = On line arrangements in the hyperbolic plane
 | volume = 23
 | year = 2002| doi-access = free
 }}
*{{citation
 | last = Edelsbrunner | first = H. | author-link = Herbert Edelsbrunner
 | isbn = 978-3-540-13722-1
 | publisher = Springer-Verlag
 | series = EATCS Monographs in Theoretical Computer Science
 | title = Algorithms in Combinatorial Geometry
 | year = 1987}}
*{{citation
 | last1 = Edelsbrunner | first1 = H. | author1-link = Herbert Edelsbrunner
 | last2 = Guibas | first2 = L. J. | author2-link = Leonidas J. Guibas
 | doi = 10.1016/0022-0000(89)90038-X
 | issue = 1
 | journal = [[Journal of Computer and System Sciences]]
 | pages = 165–194
 | title = Topologically sweeping an arrangement
 | volume = 38
 | year = 1989| doi-access = free
 }}
*{{citation
 | last1 = Edelsbrunner | first1 = H. | author1-link = Herbert Edelsbrunner
 | last2 = Guibas | first2 = L. J. | author2-link = Leonidas J. Guibas
 | last3 = Sharir | first3 = M. | author3-link = Micha Sharir
 | doi = 10.1007/BF02187784
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | pages = 161–196
 | title = The complexity and construction of many faces in arrangements of lines and of segments
 | volume = 5
 | year = 1990| doi-access = free
 }}
*{{citation
 | last1 = Edelsbrunner | first1 = H. | author1-link = Herbert Edelsbrunner
 | last2 = O'Rourke | first2 = J. | author2-link = Joseph O'Rourke (professor)
 | last3 = Seidel | first3 = R. | author3-link = Raimund Seidel
 | doi = 10.1137/0215024
 | issue = 2
 | journal = [[SIAM Journal on Computing]]
 | pages = 341–363
 | title = Constructing arrangements of lines and hyperplanes with applications
 | volume = 15
 | year = 1986}}
*{{citation
 | last1 = Edelsbrunner | first1 = H. | author1-link = Herbert Edelsbrunner
 | last2 = Welzl | first2 = E. | author2-link = Emo Welzl
 | doi = 10.1137/0215019
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | pages = 271–284
 | title = Constructing belts in two-dimensional arrangements with applications
 | volume = 15
 | year = 1986}}
*{{citation
 | last = Eppstein
 | first = D.
 | author-link = David Eppstein
 | year = 2006
 | issue = 1, R79
 | journal = [[Electronic Journal of Combinatorics]]
 | pages = 1–14
 | title = Cubic partial cubes from simplicial arrangements
 | url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html
 | volume = 13
 | doi = 10.37236/1105
 | arxiv = math.CO/0510263
 | mr = 2255421
 | s2cid = 8608953
 | access-date = 2024-10-16
 | archive-date = 2012-02-14
 | archive-url = https://web.archive.org/web/20120214071017/http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html
 | url-status = live
 }}
*{{citation
 | last1 = Eppstein | first1 = D. | author1-link = David Eppstein
 | last2 = Falmagne | first2 = J.-Cl. | author2-link = Jean-Claude Falmagne
 | last3 = Ovchinnikov | first3 = S.
 | publisher = Springer-Verlag
 | title = Media Theory
 | year = 2007}}
*{{citation
 | last1 = Eppstein
 | first1 = D.
 | author1-link = David Eppstein
 | last2 = Hart
 | first2 = D.
 | contribution = Shortest paths in an arrangement with {{mvar|k}} line orientations
 | year = 1999
 | pages = 310–316
 | title = Proceedings of the 10th ACM–SIAM Symposium on Discrete Algorithms (SODA '99)
 | contribution-url = http://portal.acm.org/citation.cfm?id=314580
 | title-link = Symposium on Discrete Algorithms
 }}
*{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Lovász | first2 = L. | author2-link = László Lovász
 | last3 = Simmons | first3 = A.
 | last4 = Straus | first4 = E. G. | author4-link = Ernst G. Straus
 | contribution = Dissection graphs of planar point sets
 | location = Amsterdam
 | pages = 139–149
 | publisher = North-Holland
 | title = A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971)
 | year = 1973
 | mr = 363986}}
*{{citation
 | last = Erickson
 | first = J.
 | title = Shortest paths in line arrangements
 | url = http://compgeom.cs.uiuc.edu/~jeffe/open/algo.html#shortpath
 | year = 1997
 | access-date = 2008-12-15
 | archive-url = https://web.archive.org/web/20081203224416/http://compgeom.cs.uiuc.edu/%7Ejeffe/open/algo.html#shortpath
 | archive-date = 2008-12-03
 | url-status = dead
 }}
*{{citation
 | last1 = Fortune | first1 = S.
 | last2 = Milenkovic | first2 = V.
 | contribution = Numerical stability of algorithms for line arrangements
 | doi = 10.1145/109648.109685
 | pages = 334–341
 | title = Proc. 7th ACM Symposium on Computational Geometry (SoCG '91)
 | year = 1991| title-link = Symposium on Computational Geometry
 | isbn = 978-0897914260
 | citeseerx = 10.1.1.56.2404
 | s2cid = 2861855
 }}
*{{citation
 | last1 = de Fraysseix | first1 = H.
 | last2 = Ossona de Mendez | first2 = P. | author2-link = Patrice Ossona de Mendez
 | contribution = Stretching of Jordan arc contact systems
 | edition = 2912
 | pages = 71–85
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Proceedings of the 11th International Symposium on Graph Drawing (GD 2003)
 | year = 2003| title-link = International Symposium on Graph Drawing
 }}
*{{citation
 | last1 = Füredi
 | first1 = Z.
 | author1-link = Zoltán Füredi
 | last2 = Palásti
 | first2 = I.
 | author2-link = Ilona Palásti
 | issue = 4
 | journal = [[Proceedings of the American Mathematical Society]]
 | pages = 561–566
 | title = Arrangements of lines with a large number of triangles
 | url = http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_palasti_lines.pdf
 | volume = 92
 | year = 1984
 | doi = 10.2307/2045427
 | jstor = 2045427
 | access-date = 2008-12-15
 | archive-date = 2016-03-03
 | archive-url = https://web.archive.org/web/20160303211253/http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_palasti_lines.pdf
 | url-status = dead
 }}
*{{citation
 | last1 = Goodman | first1 = Jacob E. | author1-link = Jacob E. Goodman
 | last2 = Pollack | first2 = Richard | author2-link = Richard M. Pollack
 | editor-last = Pach | editor-first = János | editor-link = János Pach
 | contribution = Allowable sequences and order types in discrete and computational geometry
 | doi = 10.1007/978-3-642-58043-7_6
 | location = Berlin
 | mr = 1228041
 | pages = 103–134
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = New Trends in Discrete and Computational Geometry
 | volume = 10
 | year = 1993}}
*{{citation
 | last1 = Goodman | first1 = Jacob E. | author1-link = Jacob E. Goodman
 | last2 = Pollack | first2 = Richard | author2-link = Richard M. Pollack
 | last3 = Wenger | first3 = Rephael
 | last4 = Zamfirescu | first4 = Tudor
 | doi = 10.1007/BF01212978
 | issue = 3
 | journal = [[Combinatorica]]
 | mr = 1305899
 | pages = 301–306
 | title = Every arrangement extends to a spread
 | volume = 14
 | year = 1994| s2cid = 42055590 }}
*{{citation
 | last1 = Greene | first1 = D.
 | last2 = Yao | first2 = F. F. | author2-link = Frances Yao
 | contribution = Finite-resolution computational geometry
 | doi = 10.1109/SFCS.1986.19
 | pages = 143–152
 | title = Proceedings of the 27th IEEE Symposium on Foundations of Computer Science (FOCS '86)
 | year = 1986| title-link = Symposium on Foundations of Computer Science
 | isbn = 978-0-8186-0740-0
 | s2cid = 2624319
 }}
*{{citation
 | last = Grünbaum | first = B. | author-link = Branko Grünbaum
 | location = Providence, R.I.
 | publisher = American Mathematical Society
 | series = Regional Conference Series in Mathematics
 | title = Arrangements and Spreads
 | volume = 10
 | year = 1972}}
*{{citation
 | last = Grünbaum | first = B. | author-link = Branko Grünbaum
 | title = Lectures on Arrangements
 | hdl = 1773/15699
 | year = 1974
 | publisher = University of Washington}}
*{{citation
 | last = Grünbaum | first = Branko | author-link = Branko Grünbaum
 | issue = 1
 | journal = [[Geombinatorics]]
 | mr = 1633757
 | pages = 154–159
 | title = How many triangles?
 | url = https://faculty.washington.edu/moishe/branko/BG223.How.many.triangles.pdf
 | volume = 8
 | year = 1998}}
*{{citation
 | last = Grünbaum | first = Branko | author-link = Branko Grünbaum
 | doi = 10.26493/1855-3974.88.e12
 | hdl = 1773/2269
 | issue = 1
 | journal = Ars Mathematica Contemporanea
 | mr = 2485643
 | pages = 1–25
 | title = A catalogue of simplicial arrangements in the real projective plane
 | volume = 2
 | year = 2009| doi-access = free
 | hdl-access = free
 }}
*{{citation
 | last1 = Halperin | first1 = D.
 | last2 = Sharir | first2 = M.
 | editor1-last = Goodman | editor1-first = Jacob E.
 | editor2-last = O'Rourke | editor2-first = Joseph
 | editor3-last = Tóth | editor3-first = Csaba D.
 | contribution = Arrangements
 | edition = 3rd
 | isbn = 978-1-4987-1139-5
 | mr = 3793131
 | pages = 723–762
 | publisher = CRC Press | location = Boca Raton, Florida
 | series = Discrete Mathematics and its Applications
 | title = Handbook of Discrete and Computational Geometry
 | year = 2018}}
*{{citation
 | last1 = Halperin | first1 = Dan | author1-link = Dan Halperin
 | last2 = Har-Peled | first2 = Sariel
 | last3 = Mehlhorn | first3 = Kurt | author3-link = Kurt Mehlhorn
 | last4 = Oh | first4 = Eunjin
 | last5 = Sharir | first5 = Micha | author5-link = Micha Sharir
 | doi = 10.1007/s00454-021-00338-9
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | mr = 4376573
 | pages = 439–461
 | title = The maximum-level vertex in an arrangement of lines
 | volume = 67
 | year = 2022| arxiv = 2003.00518
 }}
*{{citation
 | doi = 10.4153/CJM-1958-024-6
 | last1 = Kelly | first1 = L. M. | author1-link = Leroy Milton Kelly
 | last2 = Moser | first2 = W. O. J.
 | journal = [[Canadian Journal of Mathematics]]
 | pages = 210–219
 | title = On the number of ordinary lines determined by {{mvar|n}} points
 | volume = 10
 | year = 1958| doi-access = free
 }}
*{{citation
 | last = Klee | first = R.
 | location = Dresden
 | publisher = Focken & Oltmanns
 | title = Über die einfachen Konfigurationen der euklidischen und der projektiven Ebene
 | year = 1938}}
*{{citation
 | last = Leighton | first = F. T. | author-link = F. Thomson Leighton
 | location = Cambridge, MA
 | publisher = MIT Press
 | series = Foundations of Computing Series
 | title = Complexity Issues in VLSI: Optimal Layouts for the Shuffle–Exchange Graph and Other Networks
 | year = 1983}}
*{{citation
 | last = Levi | first = F. | authorlink = Friedrich Wilhelm Levi
 | journal = Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig
 | pages = 256–267
 | title = Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade
 | volume = 78
 | year = 1926}}
*{{citation|last=Likhtarov|first= Anton|title=Shortest Paths in Line Arrangements|publisher=University of British Columbia|type=master's thesis|doi=10.14288/1.0389809 |year=2020}}
*{{citation
 | last = Lovász | first = L. | author-link = László Lovász
 | journal = Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica
 | pages = 107–108
 | title = On the number of halving lines
 | volume = 14
 | year = 1971}}
*{{citation
 | last = Martin | first = George E.
 | isbn = 0-387-90694-0
 | mr = 1410263
 | publisher = Springer-Verlag
 | series = Undergraduate Texts in Mathematics
 | title = The Foundations of Geometry and the Non-Euclidean Plane
 | year = 1996}}
*{{citation
 | last = Matoušek | first = J. | authorlink = Jiří Matoušek (mathematician)
 | doi = 10.1007/BF02574679
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | pages = 129–134
 | title = Lower bounds on the length of monotone paths in arrangements
 | volume = 6
 | year = 1991| doi-access = free
 }}
*{{citation
 | last = Melchior | first = E. | authorlink = Eberhard Melchior
 | journal = [[Deutsche Mathematik]]
 | pages = 461–475
 | title = Über Vielseite der projektiven Ebene
 | volume = 5
 | year = 1940}}
*{{citation
 | last = Milenkovic | first = V.
 | contribution = Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic
 | doi = 10.1109/SFCS.1989.63525
 | pages = 500–505
 | title = Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (FOCS '89)
 | year = 1989| title-link = Symposium on Foundations of Computer Science
 | isbn = 978-0-8186-1982-3
 | s2cid = 18564700
 }}
*{{citation
 | last1 = Moreno | first1 = José Pedro
 | last2 = Prieto-Martínez | first2 = Luis Felipe
 | hdl = 10486/705416
 | issue = 1
 | journal = La Gaceta de la Real Sociedad Matemática Española
 | language = es
 | mr = 4225268
 | pages = 111–130
 | title = El problema de los triángulos de Kobon
 | trans-title = The Kobon triangles problem
 | volume = 24
 | year = 2021}}
*{{citation
 | last = Ovchinnikov | first = Sergei
 | doi = 10.1007/978-1-4614-0797-3
 | isbn = 978-1-4614-0796-6
 | mr = 3014880
 | publisher = Springer | location = New York
 | series = Universitext
 | title = Graphs and Cubes
 | year = 2011}}
*{{citation
 | last = Polster | first = Burkard | author-link = Burkard Polster
 | doi = 10.1007/978-1-4419-8526-2
 | isbn = 0-387-98437-2
 | mr = 1640615
 | publisher = Springer-Verlag, New York
 | series = Universitext
 | title = A Geometrical Picture Book
 | year = 1998}}
*{{citation
 | doi = 10.1016/0012-365X(79)90018-9
 | last = Purdy | first = G. B. | authorlink = George B. Purdy
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | pages = 157–163
 | title = Triangles in arrangements of lines
 | volume = 25
 | year = 1979
 | issue = 2| doi-access = free
 }}
*{{citation
 | last = Purdy | first = G. B. | authorlink = George B. Purdy
 | journal = [[Proceedings of the American Mathematical Society]]
 | pages = 77–81
 | title = Triangles in arrangements of lines, II
 | volume = 79
 | year = 1980
 | doi = 10.1090/S0002-9939-1980-0560588-4| doi-access = free
 }}
*{{citation
 | last = Roudneff | first = J.-P.
 | doi = 10.1007/BF02187900
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | pages = 97–102
 | title = Arrangements of lines with a minimum number of triangles are simple
 | volume = 3
 | year = 1988| doi-access = free
 }}
*{{citation|first=Marcus|last=Schaefer|contribution=Complexity of some geometric and topological problems|contribution-url=http://ovid.cs.depaul.edu/documents/convex.pdf|title=Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|volume=5849|pages=334–344|doi=10.1007/978-3-642-11805-0_32|year=2010|title-link=International Symposium on Graph Drawing|isbn=978-3-642-11804-3|doi-access=free|access-date=2024-10-16|archive-date=2021-06-26|archive-url=https://web.archive.org/web/20210626212759/http://ovid.cs.depaul.edu/documents/convex.pdf|url-status=live}}
*{{citation
 | last = Shor | first = P. W. | authorlink = Peter Shor
 | contribution = Stretchability of pseudolines is NP-hard
 | editor1-last = Gritzmann | editor1-first = P.
 | editor2-last = Sturmfels | editor2-first = B. | editor2-link = Bernd Sturmfels
 | location = Providence, R.I.
 | pages = 531–554
 | publisher = American Mathematical Society
 | series = DIMACS Series in Discrete Mathematics and Theoretical Computer Science
 | title = Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift
 | volume = 4
 | year = 1991| title-link = Victor Klee }}
*{{cite OEIS|A000124|Central polygonal numbers (the Lazy Caterer's sequence)|mode=cs2|ref={{harvid|Sloane}}}}
*{{citation
 | last = Steiner | first = J. | author-link = Jakob Steiner
 | journal = [[Crelle's Journal|J. Reine Angew. Math.]]
 | pages = 349–364
 | title = Einige Gesetze über die Theilung der Ebene und des Raumes
 | volume = 1
 | year = 1826| doi = 10.1515/crll.1826.1.349 | s2cid = 120477563 }}
*{{citation
 | doi = 10.1016/0097-3165(77)90022-X
 | last = Strommer | first = T. O.
 | journal = Journal of Combinatorial Theory, Series A
 | pages = 314–320
 | title = Triangles in arrangements of lines
 | volume = 23
 | year = 1977
 | issue = 3| doi-access = free
 }}
*{{citation
 | last = Székely
 | first = L. A.
 | doi = 10.1017/S0963548397002976
 | issue = 3
 | journal = [[Combinatorics, Probability and Computing]]
 | pages = 353–358
 | title = Crossing numbers and hard Erdős problems in discrete geometry
 | volume = 6
 | year = 1997
 | s2cid = 36602807
 | url = http://www.cs.tau.ac.il/~michas/szekely.pdf
 | access-date = 2024-10-16
 | archive-date = 2017-08-08
 | archive-url = https://web.archive.org/web/20170808232112/http://www.cs.tau.ac.il/~michas/szekely.pdf
 | url-status = live
 }}
*{{citation
 | last = Tóth | first = G.
 | doi = 10.1007/s004540010022
 | issue = 2
 | journal = [[Discrete & Computational Geometry]]
 | pages = 187–194
 | title = Point sets with many {{mvar|k}}-sets
 | volume = 26
 | year = 2001| doi-access = free
 }}
*{{citation
 | last = Wang | first = Haitao
 | editor1-last = Bringmann | editor1-first = Karl
 | editor2-last = Chan | editor2-first = Timothy M. | editor2-link = Timothy M. Chan
 | contribution = A simple algorithm for computing the zone of a line in an arrangement of lines
 | doi = 10.1137/1.9781611977066.7
 | pages = 79–86
 | publisher = SIAM
 | title = 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, Virtual Conference, January 10-11, 2022
 | year = 2022a| arxiv = 2111.08238
 }}
*{{citation
 | last = Wang | first = Haitao
 | editor1-last = Naor | editor1-first = Joseph (Seffi) | editor1-link = Joseph Seffi Naor
 | editor2-last = Buchbinder | editor2-first = Niv
 | contribution = Constructing many faces in arrangements of lines and segments
 | doi = 10.1137/1.9781611977073.123
 | pages = 3168–3180
 | publisher = SIAM
 | title = Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022
 | year = 2022b| arxiv = 2110.08669
 }}
{{refend}}

== External links ==
* [http://geometry.inf.ethz.ch/christt/linearr/ Database of Combinatorially Different Line Arrangements]

{{DEFAULTSORT:Arrangement Of Lines}}
[[Category:Discrete geometry]]
[[Category:Euclidean plane geometry]]