Arrangement of lines
In
Definition
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
- The cells or chambers of the arrangement are two-dimensional regions not part of any line. They form the interiors of bounded connected componentsof 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
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,[2] although in this case the unbounded cells may have infinitely many sides.[3]
Complexity of arrangements
The study of arrangements was begun by Jakob Steiner, who proved the first bounds on the maximum number of features of different types that an arrangement may have.[4] The most straightforward features to count are the vertices, edges, and cells:
- An arrangement with lines has at most vertices (a triangular number), one per pair of crossing lines. This maximum is achieved 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.[5]
- Any arrangement can be rotated to avoid axis-parallel lines, without changing its number of cells. Any arrangement with no axis-parallel lines has infinite-downward rays, one per line. These rays separate 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 lines, . Adding the unbounded and bounded cells, the total number of cells in an arrangement can be at most .[5] These are the numbers of the lazy caterer's sequence.[6]
- The number of edges of the arrangement is at most , 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. Again, this worst-case bound is achieved for simple arrangements.[5]
More complex features go by the names of "zones", "levels", and "many faces":
- The zone of a line in a line arrangement is the collection of cells having edges belonging to . 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 line is at most ,[7] and the total number of edges of the cells belonging to both sides of is at most .[8] More generally, the total complexity of the cells of a line arrangement that are intersected by any convex curve is , where denotes the inverse Ackermann function, as may be shown using Davenport–Schinzel sequences.[9] The sum of squares of cell complexities in an arrangement is , as can be shown by summing the zones of all lines.[10]
- The -level of an arrangement is the polygonal chain formed by the edges that have exactly other lines directly below them. The -level is the portion of the arrangement below the -level. Finding matching upper and lower bounds for the complexity of a -level remains a major open problem in discrete geometry. The best upper bound is , while the best lower bound is .[11] In contrast, the maximum complexity of the -level is known to be .[12] A -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 -levels: there exist arrangements and monotone paths in these arrangements where the number of points at which the path changes direction is .[13]
- 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 at most ,[14] 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:[15] if cells have a total of edges, one can form a graph with nodes (one per cell) and 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 crossings in this drawing. However, by the crossing number inequality, there are crossings. In order to satisfy both bounds, must be .[16]
Projective arrangements and projective duality
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.[17] 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.[18] 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.[19]
Due to
Triangles in arrangements
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.[21] Three infinite families of simplicial line arrangements are known:
- A near-pencil consisting of 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 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.[22] As
The
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 triangles. Every arrangement that has only triangles must be simple.[27] For Euclidean rather than projective arrangements, the minimum number of triangles is , by Roberts's triangle theorem.[28] The maximum possible number of triangular faces in a simple arrangement is known to be upper bounded by and lower bounded by ; the lower bound is achieved by certain subsets of the diagonals of a regular -gon.[29] For non-simple arrangements the maximum number of triangles is similar but more tightly bounded.[30] 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. For some but not all values of , triangles are possible.[31]
Multigrids and rhombus tilings
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.[32]
de Bruijn (1981) 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.[33]
There also exist three infinite simplicial arrangements formed from sets of parallel lines. The
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 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 of .[7] However, the memory requirements of this algorithm are high, so it may be more convenient to report all features of an arrangement by an algorithm that does not keep the entire arrangement in memory at once. This may again be done efficiently, in time and space , by an algorithmic technique known as topological sweeping.[35] 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 efficiently with limited numerical precision.[36]
As well, researchers have studied efficient algorithms for constructing smaller portions of an arrangement, such as zones,[37] -levels,[38] or the set of cells containing a given set of points.[39] 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.[40]
Marc van Kreveld suggested the algorithmic problem of computing
Non-Euclidean line arrangements
A pseudoline arrangement is a family of
Another type of non-Euclidean geometry is the hyperbolic plane, and
arrangements of hyperbolic lines in this geometry have also been studied.
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
- ^ Grünbaum (1972), p. 4.
- ^ Eppstein, Falmagne & Ovchinnikov (2007), pp. 177–178.
- ^ Ovchinnikov (2011), p. 210.
- ^ Steiner (1826); Agarwal & Sharir (2000).
- ^ a b c Halperin & Sharir (2018), p. 724.
- ^ Sloane, N. J. A. (ed.), "Sequence A000124 (Central polygonal numbers (the Lazy Caterer's sequence))", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
- ^ a b Chazelle, Guibas & Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke & Seidel (1986).
- ^ Bern et al. (1991); an unpublished manuscript of Rom Pinchasi from 2011 claims the slightly stronger bound .
- ^ Bern et al. (1991).
- ^ Aronov, Matoušek & Sharir (1994).
- ^ Dey (1998); Tóth (2001). The problem of bounding the complexity of k-levels was first studied by Lovász (1971) and Erdős et al. (1973).
- ^ Alon & Győri (1986).
- ^ Balogh et al. (2004); see also Matoušek (1991).
- ^ Canham (1969); Clarkson et al. (1990).
- ^ Ajtai et al. (1982); Leighton (1983).
- ^ Székely (1997).
- ^ Goodman & Pollack (1993), p. 109 Archived 2023-01-01 at the Wayback Machine: "The natural setting for arrangements of lines is the real projective plane"
- ^ Polster (1998), p. 223.
- ^ Goodman & Pollack (1993), p. 110.
- ^ This is the earliest proof cited by Borwein & Moser (1990), but they write that the same proof was likely given "much earlier by others".
- ^ Melchior (1940); Grünbaum (2009).
- ^ Grünbaum (1972); Grünbaum (2009).
- ^ Grünbaum (2009).
- ^ Crowe & McKee (1968); Dirac (1951); Kelly & Moser (1958); Grünbaum (1972), page 18.
- ^ Eppstein, Falmagne & Ovchinnikov (2007), p. 180.
- ^ Eppstein (2006).
- ^ Grünbaum (1972); Levi (1926); Roudneff (1988).
- ^ Grünbaum (1972).
- ^ Füredi & Palásti (1984); Grünbaum (1972).
- ^ Purdy (1979); Purdy (1980); Strommer (1977).
- ^ Moreno & Prieto-Martínez (2021).
- ^ Klee (1938).
- ^ de Bruijn (1981).
- ^ Abramenko & Brown (2008).
- ^ Edelsbrunner & Guibas (1989).
- ^ Fortune & Milenkovic (1991); Greene & Yao (1986); Milenkovic (1989).
- ^ Aharoni et al. (1999).
- ^ Agarwal et al. (1998); Chan (1999); Cole, Sharir & Yap (1987); Edelsbrunner & Welzl (1986).
- ^ Agarwal (1990); Agarwal, Matoušek & Sharir (1998); Edelsbrunner, Guibas & Sharir (1990).
- ^ Cole et al. (1989).
- ^ Erickson (1997).
- ^ Bose et al. (1996).
- ^ Eppstein & Hart (1999).
- ^ Grünbaum (1972); Agarwal & Sharir (2002).
- ^ This definition is from Grünbaum (1972). For a comparison of alternative definitions of pseudolines, see Eppstein, Falmagne & Ovchinnikov (2007).
- ^ Shor (1991); Schaefer (2010).
- ^ Goodman et al. (1994).
- ^ Dress, Koolen & Moulton (2002).
- ^ Martin (1996), pp. 41, 338.
- ^ a b de Fraysseix & Ossona de Mendez (2003).
- ^ Here an alternative definition from Shor (1991), that a pseudoline is the image of a line under a homeomorphism of the plane, is appropriate.
References
- Abramenko, Peter; Brown, Kenneth S. (2008), Buildings: Theory and Applications, Graduate Texts in Mathematics, vol. 248, New York: Springer, MR 2439729; see Example 10.14, pp. 519–520
- hdl:1874/17088
- Agarwal, P. K.; Sharir, M. (2000), "Arrangements and their applications" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 49–119, archived (PDF) from the original on 2021-04-11, retrieved 2018-11-11
- Agarwal, P. K.; Sharir, M. (2002), "Pseudo-line arrangements: duality, algorithms, and applications", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco: Society for Industrial and Applied Mathematics, pp. 800–809
- Ageev, A. A. (1996), "A triangle-free circle graph with chromatic number 5",
- Aharoni, Y.; Halperin, D.; Hanniel, I.; ISBN 978-3-540-66427-7
- MR 0806962
- Artés, J. C.; (PDF) from the original on 2010-07-18, retrieved 2008-12-15
- Balogh, J.; Regev, O.; Smyth, C.; Steiger, W.;
- Bern, M. W.; MR 1143288
- S2CID 122052678
- Bose, P.; Evans, W.; Kirkpatrick, D. G.; McAllister, M.; Snoeyink, J. (1996), "Approximating shortest paths in arrangements of lines", Proc. 8th Canadian Conf. Computational Geometry, pp. 143–148
- de Bruijn, N. G. (1981), "Algebraic theory of Penrose's non-periodic tilings of the plane" (PDF), Indagationes Mathematicae, 43: 38–66, archived (PDF) from the original on 2021-05-07, retrieved 2008-12-14
- Canham, R. J. (1969), "A theorem on arrangements of lines in the plane", S2CID 123541779
- Chan, T. (1999), Remarks on k-level algorithms in the plane, archived from the original on 2010-11-04
- S2CID 122411548
- Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.; MR 1004799
- Cole, R.; doi:10.1137/0216005
- Crowe, D. W.; McKee, T. A. (1968), "Sylvester's problem on collinear points", JSTOR 2687957
- Dey, T. L. (1998), "Improved bounds for planar k-sets and related problems", MR 1608878
- Dress, A.; Koolen, J. H.; Moulton, V. (2002), "On line arrangements in the hyperbolic plane", European Journal of Combinatorics, 23 (5): 549–557, MR 1931939
- ISBN 978-3-540-13722-1
- doi:10.1137/0215024
- doi:10.1137/0215019
- from the original on 2012-02-14, retrieved 2008-12-14
- Eppstein, D.; Falmagne, J.-Cl.; Ovchinnikov, S. (2007), Media Theory, Springer-Verlag
- Eppstein, D.; Hart, D. (1999), "Shortest paths in an arrangement with k line orientations", Proceedings of the 10th ACM–SIAM Symposium on Discrete Algorithms (SODA '99), pp. 310–316
- MR 0363986
- Erickson, J. (1997), Shortest paths in line arrangements, archived from the original on 2008-12-03, retrieved 2008-12-15
- Fortune, S.; Milenkovic, V. (1991), "Numerical stability of algorithms for line arrangements", S2CID 2861855
- de Fraysseix, H.; Ossona de Mendez, P. (2003), "Stretching of Jordan arc contact systems", Proceedings of the 11th International Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science (2912 ed.), Springer-Verlag, pp. 71–85
- (PDF) from the original on 2016-03-03, retrieved 2008-12-15
- MR 1228041
- S2CID 42055590
- Greene, D.; S2CID 2624319
- Grünbaum, B. (1972), Arrangements and Spreads, Regional Conference Series in Mathematics, vol. 10, Providence, R.I.: American Mathematical Society
- hdl:1773/15699; see p. 6 of "Euclidean arrangements" (p. 101 of linked pdf)
- MR 2485643
- Halperin, D.; Sharir, M. (2018), "Arrangements", in Goodman, Jacob E.; O'Rourke, Joseph; Tóth, Csaba D. (eds.), Handbook of Discrete and Computational Geometry, Discrete Mathematics and its Applications (3rd ed.), Boca Raton, Florida: CRC Press, pp. 723–762, MR 3793131
- Klee, R. (1938), Über die einfachen Konfigurationen der euklidischen und der projektiven Ebene, Dresden: Focken & Oltmanns
- Leighton, F. T. (1983), Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press
- Levi, F. (1926), "Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade", Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipzig, 78: 256–267
- Lovász, L. (1971), "On the number of halving lines", Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica, 14: 107–108
- Martin, George E. (1996), The foundations of geometry and the non-Euclidean plane, Undergraduate Texts in Mathematics, Springer-Verlag, MR 1410263
- Melchior, E. (1940), "Über Vielseite der projektiven Ebene", Deutsche Mathematik, 5: 461–475
- Milenkovic, V. (1989), "Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic", S2CID 18564700
- Moreno, José Pedro; Prieto-Martínez, Luis Felipe (2021), "El problema de los triángulos de Kobon" [The Kobon triangles problem], La Gaceta de la Real Sociedad Matemática Española (in Spanish), 24 (1): 111–130, MR 4225268
- JSTOR 1990609
- Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, New York: Springer, MR 3014880
- MR 1640615
- Roudneff, J.-P. (1988), "Arrangements of lines with a minimum number of triangles are simple",
- Schaefer, Marcus (2010), "Complexity of some geometric and topological problems" (PDF), ISBN 978-3-642-11804-3, archived(PDF) from the original on 2021-06-26, retrieved 2011-02-25
- Shor, P. W. (1991), "Stretchability of pseudolines is NP-hard", in Gritzmann, P.; Sturmfels, B. (eds.), Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, Providence, R.I.: American Mathematical Society, pp. 531–554
- S2CID 120477563
- Strommer, T. O. (1977), "Triangles in arrangements of lines", Journal of Combinatorial Theory, Series A, 23 (3): 314–320,
- Székely, L. A. (1997), "Crossing numbers and hard Erdős problems in discrete geometry" (PDF), (PDF) from the original on 2017-08-08, retrieved 2019-09-23
- Tóth, G. (2001), "Point sets with many k-sets",