Disposición de las líneas

En geometría, una disposición de líneas es la subdivisión del plano euclidiano formada por un conjunto finito de líneas. Una disposición consta de polígonos convexos acotados y no acotados , las celdas de la disposición; segmentos de línea y rayos , las aristas de la disposición; y puntos donde se cruzan dos o más líneas, los vértices de la disposición. Cuando se considera en el plano proyectivo en lugar del plano euclidiano, cada dos líneas se cruzan, y una disposición es el dual proyectivo de un conjunto finito de puntos. Las disposiciones de líneas también se han considerado en el plano hiperbólico y se han generalizado a pseudolíneas , curvas que tienen propiedades topológicas similares a las de las líneas. El estudio inicial de las disposiciones se atribuye a un artículo de Jakob Steiner de 1826 .

Se dice que una disposición es simple cuando, como máximo, dos líneas se cruzan en cada vértice, y simplicial cuando todas las celdas son triángulos (incluidas las celdas no acotadas, como subconjuntos del plano proyectivo). Existen tres familias infinitas conocidas de disposiciones simpliciales, así como muchas disposiciones simpliciales esporádicas que no se ajustan a ninguna familia conocida. También se han considerado disposiciones para sistemas de líneas infinitos pero localmente finitos. Ciertas disposiciones infinitas de líneas paralelas pueden formar disposiciones simpliciales, y una forma de construir el teselado de Penrose aperiódico implica encontrar la gráfica dual de una disposición de líneas que forman cinco subconjuntos paralelos.

El número máximo de celdas, aristas y vértices, para disposiciones con un número dado de líneas, es una función cuadrática del número de líneas. Estos máximos se alcanzan con disposiciones simples. La complejidad de otras características de las disposiciones se ha estudiado en geometría discreta ; estas incluyen zonas , las celdas que tocan una sola línea, y niveles , las cadenas poligonales por las que pasa un número dado de líneas. El teorema del triángulo de Roberts y el problema del triángulo de Kobon tratan sobre el número mínimo y máximo de celdas triangulares en una disposición euclidiana, respectivamente.

En geometría computacional, se conocen algoritmos para construir las características de una disposición en un tiempo proporcional al número de características y en un espacio lineal con respecto al número de líneas. Asimismo, los investigadores han estudiado algoritmos eficientes para construir porciones más pequeñas de una disposición y para problemas como el de la ruta más corta en los vértices y aristas de la misma.

Como experimento mental informal , consideremos cortar una hoja de papel infinita a lo largo de un número finito de líneas. Estos cortes dividirían el papel en polígonos convexos . Sus aristas serían segmentos de línea unidimensionales o rayos , con vértices en los puntos donde se cruzan dos líneas de corte. Esto se puede formalizar matemáticamente clasificando los puntos del plano según en qué lado de cada línea se encuentran. Cada línea produce tres posibilidades por punto: el punto puede estar en uno de los dos semiplanos abiertos a cada lado de la línea, o puede estar sobre la línea. Dos puntos pueden considerarse equivalentes si tienen la misma clasificación con respecto a todas las líneas. Esta es una relación de equivalencia , cuyas clases de equivalencia son subconjuntos de puntos equivalentes. Estos subconjuntos subdividen el plano en formas de los siguientes tres tipos: ^{[ 1 ]}

1. Las celdas o cámaras de la disposición son regiones bidimensionales que no forman parte de ninguna línea. Constituyen el interior de polígonos convexos delimitados o regiones convexas no delimitadas. Son los componentes conexos de los puntos que quedarían después de eliminar todos los puntos de las líneas. ^{[ 1 ]}
2. Los bordes o paneles de la disposición son regiones unidimensionales pertenecientes a una sola línea. Son los segmentos de línea abiertos y los rayos infinitos abiertos en los que cada línea se divide por sus puntos de intersección con las demás líneas. Es decir, si una de las líneas es cortada por todas las demás líneas, estos son los componentes conexos de sus puntos no cortados. ^{[ 1 ]}
3. Los vértices de la disposición son puntos aislados que pertenecen a dos o más líneas, donde esas líneas se cruzan entre sí. ^{[ 1 ]}

El límite de una celda es el sistema de aristas que la tocan, y el límite de una arista es el conjunto de vértices que la tocan (un vértice para un rayo y dos para un segmento de línea). El sistema de objetos de los tres tipos, vinculados por este operador de límite, forma un complejo celular que cubre el plano. Se dice que dos disposiciones son isomorfas o combinatoriamente equivalentes si existe una correspondencia biunívoca que preserva el límite entre los objetos de sus complejos celulares asociados. ^{[ 1 ]}

La misma clasificación de puntos y las mismas formas de clases de equivalencia pueden utilizarse para arreglos infinitos pero localmente finitos , definidos como arreglos en los que cada subconjunto acotado del plano es atravesado por un número finito de líneas. ^{[ 2 ]} En este caso, las celdas no acotadas pueden tener un número infinito de lados. ^{[ 3 ]}

Es sencillo contar el número máximo de vértices, aristas y celdas en una disposición, todos los cuales son cuadráticos en el número de líneas:

• Un acuerdo con${\displaystyle n}$Las líneas tienen como máximo${\displaystyle n(n-1)/2}$vértices (un número triangular ), uno por cada par de líneas que se cruzan. Este máximo se alcanza para disposiciones simples , aquellas en las que cada dos líneas se cruzan en un vértice que es disjunto de todas las demás líneas. El número de vértices es menor cuando algunas líneas son paralelas o cuando algunos vértices son cruzados por más de dos líneas. ^{[ 4 ]}
• Una disposición puede rotarse, si es necesario, para evitar líneas paralelas a los ejes. Después de este paso, cada rayo que forma un borde de la disposición se extiende hacia arriba o hacia abajo desde su punto final; no puede ser horizontal. Hay${\displaystyle n}$rayos descendentes, uno por línea, y estos rayos separan${\displaystyle n+1}$celdas de la disposición que no están limitadas en la dirección descendente. Las celdas restantes tienen todas un único vértice inferior (nuevamente, porque no hay líneas paralelas a los ejes). Para cada par de líneas, solo puede haber una celda donde las dos líneas se encuentran en el vértice inferior, por lo que el número de celdas limitadas hacia abajo es como máximo el número de pares de líneas,${\displaystyle n(n-1)/2}$Sumando las celdas no delimitadas y delimitadas, el número total de celdas en una disposición puede ser como máximo${\displaystyle n(n+1)/2+1}$. ^{[ 5 ]} Estos son los números de la secuencia del proveedor de catering perezoso . ^{[ 6 ]}
• El número de aristas de la disposición es como máximo${\displaystyle n^{2}}$, como puede verse ya sea utilizando la característica de Euler para calcularlo a partir del número de vértices y celdas, o bien observando que cada línea se divide en como máximo${\displaystyle n}$bordes por el otro${\displaystyle n-1}$ lines. Simple arrangements have exactly ${\displaystyle n^{2}}$ edges.^[5]

More complex features go by the names of "zones", "levels", and "many faces":

• The zone of a line ${\displaystyle \ell }$ in a line arrangement is the collection of cells having edges belonging to ${\displaystyle \ell }$. 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 ${\displaystyle \ell }$ is at most ${\displaystyle 5n-1}$,^[7] and the total number of edges of the cells belonging to both sides of ${\displaystyle \ell }$ is at most ${\displaystyle \lfloor 9.5n\rfloor -1}$.^[8] More generally, the total complexity of the cells of a line arrangement that are intersected by any convex curveis ${\displaystyle O(n\alpha (n))}$, where ${\displaystyle \alpha }$ 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 ${\displaystyle O(n^{2})}$, as can be shown by summing the zones of all lines.^[10]
• The ${\displaystyle k}$-level of an arrangement is the polygonal chain formed by the edges that have exactly ${\displaystyle k}$ other lines directly below them. The ${\displaystyle \leq k}$-level is the portion of the arrangement below the ${\displaystyle k}$-level. Finding matching upper and lower bounds for the complexity of a ${\displaystyle k}$-level remains a major open problem in discrete geometry. The best upper bound known is ${\displaystyle O(nk^{1/3})}$, while the best lower bound known is ${\displaystyle n2^{\Omega ({\sqrt {\log k}})}}$.^[11] In contrast, the maximum complexity of the ${\displaystyle \leq k}$-level is known to be ${\displaystyle \Theta (nk)}$.^[12] A ${\displaystyle k}$-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 ${\displaystyle k}$-levels: there exist arrangements and monotone paths in these arrangements where the number of points at which the path changes direction is ${\displaystyle n^{2-o(1)}}$.^[13]
• Although a single cell in an arrangement may be bounded by all ${\displaystyle n}$ lines, it is not possible in general for ${\displaystyle m}$ different cells to all be bounded by ${\displaystyle n}$ lines. Rather, the total complexity of ${\displaystyle m}$ cells is at most ${\displaystyle \Theta (m^{2/3}n^{2/3}+n)}$, ^{[ 14 ]} casi la misma cota que aparece en el teorema de Szemerédi-Trotter sobre incidencias punto-línea en el plano. Una demostración sencilla de esto se deduce de la desigualdad del número de cruces : ^{[ 15 ]} si${\displaystyle m}$Las células tienen un total de${\displaystyle x+n}$bordes, se puede formar un grafo con${\displaystyle m}$nodos (uno por celda) y${\displaystyle x}$aristas (una por cada par de celdas consecutivas en la misma línea). Las aristas de este gráfico se pueden dibujar como curvas que no se cruzan dentro de las celdas correspondientes a sus puntos finales, y luego siguen las líneas de la disposición. Por lo tanto, hay${\displaystyle O(n^{2})}$cruces en este dibujo. Sin embargo, debido a la desigualdad del número de cruces, hay${\displaystyle \Omega (x^{3}/m^{2})}$cruces. Para satisfacer ambos límites,${\displaystyle x}$debe ser${\displaystyle O(m^{2/3}n^{2/3})}$. ^{[ 16 ]}

Es conveniente estudiar las disposiciones de líneas en el plano proyectivo, ya que cada par de líneas tiene un punto de intersección. ^{[ 17 ]} Las disposiciones de líneas no se pueden definir utilizando los lados de las líneas, porque una línea en el plano proyectivo no divide el plano en dos lados distintos. ^{[ 18 ]} Aun así, se pueden definir las celdas de una disposición como las componentes conexas de los puntos que no pertenecen a ninguna línea, las aristas como las componentes conexas de conjuntos de puntos que pertenecen a una sola línea, y los vértices como los puntos donde se cruzan dos o más líneas. Una disposición de líneas en el plano proyectivo difiere de su contraparte euclidiana en que los dos rayos euclidianos en cada extremo de una línea se reemplazan por una sola arista en el plano proyectivo que conecta los vértices más a la izquierda y más a la derecha de esa línea, y en que los pares de celdas euclidianas no acotadas se reemplazan en el plano proyectivo por celdas individuales que son cruzadas por la línea proyectiva en el infinito. ^{[ 19 ]}

Una disposición de líneas en el plano euclidiano puede interpretarse naturalmente como una disposición de círculos máximos en la esfera bidimensional.${\displaystyle S^{2}}$Para ver esto, inserte el plano euclidiano.${\displaystyle \mathbb {R} ^{2}}$como un plano afín${\displaystyle A\subset \mathbb {R} ^{3}}$no pasando por el origen. Cada punto de${\displaystyle A}$determina una línea que pasa por el origen, que interseca${\displaystyle S^{2}}$en un par de puntos antipodales; asimismo, cada línea en${\displaystyle A}$mapas a un círculo máximo en la esfera. El ecuador asociado con${\displaystyle A}$separa los dos hemisferios y desempeña el papel de la línea en el infinito. Identificar puntos antipodales en${\displaystyle S^{2}}$produce el plano proyectivo, donde las líneas en${\displaystyle \mathbb {R} ^{2}}$Se extienden naturalmente a círculos máximos y las líneas paralelas se encuentran en el infinito. De esta manera, la estructura combinatoria de las disposiciones de líneas, incluyendo incidencias, regiones e intersecciones, se conserva al transferirla a disposiciones de círculos máximos en la esfera. ^{[ 20 ]}

Debido a la dualidad proyectiva , muchas afirmaciones sobre las propiedades combinatorias de los puntos en el plano pueden entenderse más fácilmente en una forma dual equivalente sobre arreglos de líneas. Por ejemplo, el teorema de Sylvester-Gallai , que establece que cualquier conjunto no colineal de puntos en el plano tiene una línea ordinaria que contiene exactamente dos puntos, se transforma bajo la dualidad proyectiva en la afirmación de que cualquier arreglo proyectivo de un número finito de líneas con más de un vértice tiene un punto ordinario , un vértice donde solo se cruzan dos líneas. La primera demostración conocida del teorema de Sylvester-Gallai, realizada por Eberhard Melchior en 1940 , utiliza la característica de Euler para demostrar que tal vértice siempre debe existir. ^{[ 21 ]}

Se dice que una disposición de líneas en el plano proyectivo es simplicial si cada celda de la disposición está delimitada por exactamente tres aristas. Las disposiciones simpliciales fueron estudiadas por primera vez por Melchior. ^{[ 22 ]} Se conocen tres familias infinitas de disposiciones de líneas simpliciales:

1. Un lápiz casi perfecto que consta de${\displaystyle n-1}$líneas que pasan por un solo punto, junto con una sola línea adicional que no pasa por el mismo punto,
2. La familia de líneas formadas por los lados de un polígono regular junto con sus ejes de simetría y
3. Los lados y los ejes de simetría de un polígono regular par, junto con la línea en el infinito.

Además, existen muchos otros ejemplos de arreglos simpliciales esporádicos que no encajan en ninguna familia infinita conocida. ^{[ 23 ]} Conjeturalmente, solo hay un número finito de ellos. Se sabe que esto es cierto bajo una cota lineal en el número de puntos dobles. ^{[ 24 ]} Como escribe Branko Grünbaum , los arreglos simpliciales "aparecen como ejemplos o contraejemplos en muchos contextos de la geometría combinatoria y sus aplicaciones". ^{[ 25 ]} Por ejemplo, los arreglos simpliciales forman contraejemplos a una conjetura sobre la relación entre el grado de un conjunto de ecuaciones diferenciales y el número de líneas invariantes que pueden tener las ecuaciones. ^{[ 26 ]} Los dos contraejemplos conocidos a la conjetura de Dirac-Motzkin (que establece que cualquier${\displaystyle n}$-la disposición de la línea tiene al menos${\displaystyle n/2}$Los puntos ordinarios) son ambos simpliciales. ^{[ 27 ]}

El grafo dual de una disposición lineal tiene un nodo por celda y una arista que une cualquier par de celdas que comparten una arista de la disposición. Estos grafos son cubos parciales , grafos en los que los nodos pueden etiquetarse mediante vectores de bits de tal manera que la distancia del grafo sea igual a la distancia de Hamming entre etiquetas. En el caso de una disposición lineal, cada coordenada del etiquetado asigna 0 a los nodos de un lado de una de las líneas y 1 a los nodos del otro lado. ^{[ 28 ]} Los grafos duales de disposiciones simpliciales se han utilizado para construir familias infinitas de cubos parciales 3-regulares , isomorfos a los grafos de zonohedros simples . ^{[ 29 ]}

Una disposición con el número mínimo de triángulos según el teorema del triángulo de Roberts.

Triángulos de Kobon en una disposición de 17 líneas

También es interesante estudiar los números extremos de celdas triangulares en arreglos que no necesariamente son simpliciales. Cualquier arreglo en el plano proyectivo debe tener al menos${\displaystyle n}$triángulos. Cada arreglo que tiene solo${\displaystyle n}$Los triángulos deben ser simples. ^{[ 30 ]} Para disposiciones euclidianas en lugar de proyectivas, el número mínimo de triángulos es${\displaystyle n-2}$, por el teorema del triángulo de Roberts . ^{[ 31 ]} Se sabe que el número máximo posible de caras triangulares en una disposición simple está acotado superiormente por${\displaystyle n(n-1)/3}$y limitado inferiormente por${\displaystyle n(n-3)/3}$; el límite inferior se alcanza mediante ciertos subconjuntos de las diagonales de una matriz regular${\displaystyle 2n}$-gon. ^{[ 32 ]} Para arreglos proyectivos que no se requiere que sean simples, existen arreglos con${\displaystyle n(n-1)/3+4}$triángulos para todos${\displaystyle n\geq 4}$y todos los acuerdos con${\displaystyle n\geq 6}$tener como máximo${\displaystyle 7n(n-1)/18+1/3}$triángulos. ^{[ 33 ]} El problema del triángulo de Kobon, estrechamente relacionado , pide el número máximo de triángulos finitos no superpuestos en una disposición en el plano euclidiano, sin contar las caras no acotadas que podrían formar triángulos en el plano proyectivo. Nuevamente, no se requiere que las disposiciones sean simples. Para algunos, pero no todos, valores de${\displaystyle n}$, existen acuerdos con${\displaystyle n(n-2)/3}$triángulos. ^{[ 34 ]}

El grafo dual de una disposición simple de líneas puede representarse geométricamente como una colección de rombos , uno por cada vértice de la disposición, con lados perpendiculares a las líneas que convergen en dicho vértice. Estos rombos pueden unirse para formar un teselado de un polígono convexo en el caso de una disposición de un número finito de líneas, o de todo el plano en el caso de una disposición localmente finita con un número infinito de líneas. Esta construcción se conoce a veces como diagrama de Klee , en referencia a una publicación de Rudolf Klee de 1938 que utilizó esta técnica. Sin embargo, no todos los teselados de rombos se obtienen a partir de líneas de esta manera. ^{[ 35 ]}

En un artículo de 1981 , NG de Bruijn investigó casos especiales de esta construcción en los que la disposición de las líneas consiste en:${\displaystyle k}$conjuntos de líneas paralelas igualmente espaciadas. Para dos familias perpendiculares de líneas paralelas, esta construcción da el teselado cuadrado del plano, y para tres familias de líneas que forman ángulos de 120 grados entre sí (que a su vez forman un teselado trihexagonal ), produce el teselado rómbico . Sin embargo, para más familias de líneas, esta construcción produce teselados aperiódicos . En particular, para cinco familias de líneas que forman ángulos iguales entre sí (o, como de Bruijn llama a esta disposición, un pentágrido ), produce una familia de teselados que incluye la versión rómbica de los teselados de Penrose . ^{[ 36 ]}

Teselado cuadrado Tetrakis

Teselado triangular

Teselado hexagonal bisecado

También existen tres disposiciones simpliciales infinitas formadas por conjuntos de líneas paralelas. El teselado cuadrado tetrakis es una disposición infinita de líneas que forman un teselado periódico que se asemeja a una multigrid con cuatro familias paralelas, pero en la que dos de las familias están más espaciadas que las otras dos, y en la que la disposición es simplicial en lugar de simple. Su dual es el teselado cuadrado truncado . De manera similar, el teselado triangular es una disposición infinita de líneas simpliciales con tres familias paralelas, que tiene como dual el teselado hexagonal , y el teselado hexagonal bisecado es una disposición infinita de líneas simpliciales con seis familias paralelas y dos espaciamientos entre líneas, dual al gran teselado rombitrihexagonal . Estos tres ejemplos provienen de tres grupos de reflexión afines en el plano euclidiano, sistemas de simetrías basados ​​en la reflexión a través de cada línea en estas disposiciones. ^{[ 37 ]}

Construir una disposición significa, dada como entrada una lista de las líneas en la disposición, calcular una representación de los vértices, aristas y celdas de la disposición junto con las adyacencias entre estos objetos. Por ejemplo, estas características pueden representarse como una lista de aristas doblemente conexas . Las disposiciones pueden construirse de manera eficiente mediante un algoritmo incremental que agrega una línea a la vez a la disposición de las líneas agregadas previamente. Cada nueva línea puede agregarse en un tiempo proporcional al tamaño de su zona, lineal según el teorema de la zona. Esto resulta en un tiempo total de construcción de${\displaystyle O(n^{2})}$. ^{[ 7 ]} Los requisitos de memoria de este algoritmo también son${\displaystyle O(n^{2})}$En cambio, es posible informar sobre las características de un arreglo sin almacenarlas todas a la vez, en el tiempo.${\displaystyle O(n^{2})}$y espacio${\displaystyle O(n)}$mediante una técnica algorítmica conocida como barrido topológico. ^{[ 38 ]} Calcular una disposición de líneas con exactitud requiere una precisión numérica varias veces mayor que la de las coordenadas de entrada: si una línea se especifica mediante dos puntos en ella, las coordenadas de los vértices de la disposición pueden necesitar cuatro veces más precisión que estos puntos de entrada. Por lo tanto, los geómetras computacionales también han estudiado algoritmos para construir disposiciones con precisión numérica limitada. ^{[ 39 ]}

Además, los investigadores han estudiado algoritmos eficientes para construir porciones más pequeñas de una disposición, como zonas, ^{[ 40 ]}${\displaystyle k}$-niveles, ^{[ 41 ]} o el conjunto de celdas que contienen un conjunto dado de puntos. ^{[ 42 ]} El problema de encontrar el vértice de disposición con la mediana${\displaystyle x}$La coordenada - surge (en forma dual) en estadística robusta como el problema de calcular el estimador de Theil-Sen de un conjunto de puntos. ^{[ 43 ]}

Marc van Kreveld propuso el problema algorítmico de calcular los caminos más cortos entre vértices en una disposición lineal, donde los caminos están restringidos a seguir las aristas de la disposición, más rápidamente que el tiempo cuadrático que tomaría aplicar un algoritmo de camino más corto a todo el grafo de la disposición. ^{[ 44 ]} Se conoce un algoritmo de aproximación , ^{[ 45 ]} y el problema puede resolverse eficientemente para líneas que pertenecen a un pequeño número de familias paralelas (como es típico en las cuadrículas de calles urbanas), ^{[ 46 ]} pero el problema general sigue abierto. ^{[ 47 ]}

Una disposición de nueve pseudolíneas no estirable. (Todas las disposiciones de menos de nueve pseudolíneas son estirables). Según el teorema del hexágono de Pappus , esta disposición no puede realizarse en un plano proyectivo sobre ningún cuerpo.

Una disposición de líneas hiperbólicas combinatoriamente equivalente a un diagrama de cuerdas utilizado por Ageev (1996) para mostrar que los gráficos de círculos sin triángulos a veces pueden necesitar 5 colores .

Una disposición de pseudolíneas es una familia de curvas que comparten propiedades topológicas similares con una disposición de líneas. ^{[ 48 ]} Estas pueden definirse en el plano proyectivo como curvas cerradas simples, cualesquiera dos de las cuales se encuentran en un único punto de intersección. ^{[ 49 ]} Se dice que una disposición de pseudolíneas es estirable si es combinatoriamente equivalente a una disposición de líneas. Determinar la estirabilidad es una tarea computacional difícil: es completo para la teoría existencial de los reales distinguir las disposiciones estirables de las no estirables. ^{[ 50 ]} Toda disposición de un número finito de pseudolíneas puede extenderse de modo que se conviertan en líneas en una "expansión", un tipo de geometría de incidencia no euclidiana en la que cada dos puntos de un plano topológico están conectados por una única línea (como en el plano euclidiano), pero en la que otros axiomas de la geometría euclidiana pueden no aplicarse. ^{[ 51 ]}

Otro tipo de geometría no euclidiana es el plano hiperbólico , y también se han estudiado arreglos de líneas en esta geometría. ^{[ 52 ]} Cualquier conjunto finito de líneas en el plano euclidiano tiene un arreglo combinatoriamente equivalente en el plano hiperbólico (por ejemplo, encerrando los vértices del arreglo con un círculo grande e interpretando el interior del círculo como un modelo de Klein del plano hiperbólico). Sin embargo, los pares de líneas paralelas (que no se cruzan) están menos restringidos en arreglos de líneas hiperbólicas que en el plano euclidiano: en particular, la relación de ser paralelo es una relación de equivalencia para líneas euclidianas pero no para líneas hiperbólicas. ^{[ 53 ]} El grafo de intersección de las líneas en un arreglo hiperbólico puede ser un grafo circular arbitrario . El concepto correspondiente a los arreglos de líneas hiperbólicas para pseudolíneas es un arreglo de pseudolínea débil , ^{[ 54 ]} una familia de curvas que tienen las mismas propiedades topológicas que las líneas ^{[ 55 ]} tales que cualesquiera dos curvas en la familia o bien se encuentran en un único punto de cruce o no tienen intersección. ^{[ 54 ]}

En un estudio sobre arreglos, Pankaj Agarwal y Micha Sharir atribuyen el estudio de los arreglos a Jakob Steiner , escribiendo que "el primer artículo sobre este tema es quizás" un artículo de Steiner de 1826. ^{[ 56 ]} En este artículo, Steiner demostró límites para el número máximo de características de diferentes tipos que puede tener un arreglo. ^{[ 57 ]} Después de Steiner, el estudio de los arreglos se centró en arreglos de hiperplanos de dimensiones superiores , prestando atención a su estructura general y a las celdas individuales en estos arreglos. El estudio de los arreglos de líneas, y de características más complejas como las zonas dentro de estos arreglos, volvió a despertar interés a partir de la década de 1980 como parte de los fundamentos de la geometría computacional . ^{[ 56 ]}

• Configuración (geometría) , una disposición de líneas y un conjunto de puntos donde todas las líneas contienen el mismo número de puntos y todos los puntos pertenecen al mismo número de líneas.
• Disposición (partición del espacio) , una partición del plano dada por curvas superpuestas o de un espacio de dimensiones superiores por superficies superpuestas, sin requerir que las curvas o superficies sean planas.
• El Puente Matemático , un puente en Cambridge, Inglaterra, cuyas vigas forman una disposición de líneas tangentes a su arco.

• Base de datos de arreglos de líneas combinatoriamente diferentes