Disposición de líneas

Subdivisión del plano por líneas

Una disposición de línea simple (izquierda) y una disposición de línea simple (derecha).

En geometría , una disposición de líneas es la subdivisión del plano formado por una colección de líneas . Los problemas de contar las características de las disposiciones se han estudiado en geometría discreta y los geómetras computacionales han encontrado algoritmos para la construcción eficiente de disposiciones.

Definición

Intuitivamente, cualquier conjunto finito de líneas en el plano corta el plano en polígonos bidimensionales (celdas), segmentos de línea unidimensionales o rayos y puntos de cruce de dimensión cero. Esto se puede formalizar matemáticamente clasificando los puntos del plano según en qué lado de cada línea se encuentren. Cada línea separa el plano en dos semiplanos abiertos , y cada punto del plano tiene tres posibilidades por línea: puede estar en cualquiera de estos dos semiplanos, o puede estar en la línea misma. 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. Las celdas o cámaras del arreglo son regiones bidimensionales que no forman parte de ninguna línea. Forman el interior de polígonos convexos acotados o regiones convexas no acotadas. Si el plano se corta a lo largo de todas las líneas, estos son los componentes conectados de los puntos que permanecen sin cortar.
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 cruce con las otras líneas. Es decir, si una de las líneas es cortada por todas las demás líneas, estas son las componentes conexas de sus puntos no cortados.
3. Los vértices de la disposición son puntos aislados que pertenecen a dos o más líneas, donde dichas líneas se cruzan entre sí.

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 de celdas 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 en sus complejos de celdas asociados. ^[1]

La misma clasificación de puntos y las mismas formas de clases de equivalencia se pueden utilizar para arreglos infinitos pero localmente finitos , en los que cada subconjunto acotado del plano puede ser atravesado sólo por un número finito de líneas, ^[2] aunque en este caso las celdas no acotadas pueden tener un número infinito de lados. ^[3]

Complejidad de los acuerdos

El estudio de los arreglos fue iniciado por Jakob Steiner , quien demostró los primeros límites en el número máximo de características de diferentes tipos que un arreglo puede tener. ^[4] Las características más sencillas de contar son los vértices, los bordes y las celdas:

• Una disposición con líneas tiene como máximo vértices (un número triangular ), uno por cada par de líneas que se cruzan. Este máximo se logra 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. ^[5] ${\displaystyle n}$ ${\displaystyle n(n-1)/2}$
• Cualquier disposición puede rotarse para evitar líneas paralelas a los ejes, sin cambiar su número de celdas. Cualquier disposición sin líneas paralelas a los ejes tiene rayos infinitos hacia abajo, uno por línea. Estos rayos separan las celdas de la disposición que no tienen límites en la dirección descendente. Las celdas restantes tienen un único vértice inferior (de nuevo, 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 con límites inferiores es como máximo el número de pares de líneas, . Sumando las celdas con límites y las ilimitadas, el número total de celdas en una disposición puede ser como máximo . ^[5] Estos son los números de la secuencia del proveedor perezoso . ^[6] ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle n(n-1)/2}$ ${\displaystyle n(n+1)/2+1}$
• El número de aristas del arreglo es como máximo , ${\displaystyle n^{2}}$ como se puede ver ya sea usando la característica de Euler para calcularlo a partir de los números de vértices y celdas, o observando que cada línea está dividida en aristas como máximo por las otras líneas. Nuevamente, este límite del peor caso se logra para arreglos simples. ^[5] ${\displaystyle n}$ ${\displaystyle n-1}$

Las características más complejas reciben los nombres de "zonas", "niveles" y "muchas caras":

• La zona de una línea ${\displaystyle \ell }$ en una disposición de líneas es la colección de celdas que tienen aristas que pertenecen a . ${\displaystyle \ell }$ El teorema de la zona establece que el número total de aristas en las celdas de una sola zona es lineal. Más precisamente, el número total de aristas de las celdas que pertenecen a un solo lado de la línea ${\displaystyle \ell }$ es como máximo , ^[7] ${\displaystyle 5n-1}$ y el número total de aristas de las celdas que pertenecen a ambos lados de ${\displaystyle \ell }$ es como máximo . ^[8] ${\displaystyle \lfloor 9.5n\rfloor -1}$ De manera más general, la complejidad total de las celdas de una disposición de líneas que son intersectadas por cualquier curva convexa es , ${\displaystyle O(n\alpha (n))}$ donde denota la función inversa de Ackermann , como se puede mostrar utilizando secuencias de Davenport–Schinzel . ^[9] La suma de los cuadrados de las complejidades de las celdas en una disposición es , como se puede mostrar sumando las zonas de todas las líneas. ^[10] ${\displaystyle \alpha }$ ${\displaystyle O(n^{2})}$
• El nivel - de un arreglo es la cadena poligonal formada por los bordes que tienen exactamente otras líneas directamente debajo de ellos. El nivel - es la porción del arreglo debajo del nivel -. Encontrar límites superiores e inferiores coincidentes para la complejidad de un nivel - sigue siendo un importante problema abierto en geometría discreta. El mejor límite superior es , mientras que el mejor límite inferior es . ^[11] En contraste, se sabe que la complejidad máxima del nivel - es . ^[12] Un nivel - es un caso especial de un camino monótono en un arreglo; es decir, una secuencia de bordes que interseca cualquier línea vertical en un solo punto. Sin embargo, los caminos monótonos pueden ser mucho más complicados que los niveles -: existen arreglos y caminos monótonos en estos arreglos donde el número de puntos en los que el camino cambia de dirección es . ^[13] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \leq k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(nk^{1/3})}$ ${\displaystyle n2^{\Omega ({\sqrt {\log k}})}}$ ${\displaystyle \leq k}$ ${\displaystyle \Theta (nk)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n^{2-o(1)}}$
• Aunque una sola celda en un arreglo puede estar limitada por todas las líneas, no es posible en general que diferentes celdas estén todas limitadas por líneas. Más bien, la complejidad total de las celdas es como máximo , ^[14] casi el mismo límite que ocurre en el teorema de Szemerédi-Trotter sobre incidencias de puntos y líneas en el plano. Una prueba simple de esto se desprende de la desigualdad del número de cruces : ^[15] si las celdas tienen un total de aristas, se puede formar un grafo con nodos (uno por celda) y aristas (uno por par de celdas consecutivas en la misma línea). Las aristas de este grafo se pueden dibujar como curvas que no se cruzan dentro de las celdas correspondientes a sus puntos finales, y luego siguen las líneas del arreglo. Por lo tanto, hay cruces en este dibujo. Sin embargo, por la desigualdad del número de cruces, hay cruces. Para satisfacer ambos límites, debe ser . ^[16] ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle \Theta (m^{2/3}n^{2/3}+n)}$ ${\displaystyle m}$ ${\displaystyle x+n}$ ${\displaystyle m}$ ${\displaystyle x}$ ${\displaystyle O(n^{2})}$ ${\displaystyle \Omega (x^{3}/m^{2})}$ ${\displaystyle x}$ ${\displaystyle O(m^{2/3}n^{2/3})}$

Disposiciones proyectivas y dualidad proyectiva

Es conveniente estudiar los arreglos de líneas en el plano proyectivo , ya que cada par de líneas tiene un punto de cruce. ^[17] Los arreglos de líneas no se pueden definir utilizando los lados de las líneas, porque una línea en el plano proyectivo no separa el plano en dos lados distintos. ^[18] Uno todavía puede definir las celdas de un arreglo como los componentes conectados de los puntos que no pertenecen a ninguna línea, las aristas como los componentes conectados 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. Un arreglo 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 son reemplazados por una sola arista en el plano proyectivo que conecta los vértices más a la izquierda y más a la derecha en esa línea, y en que los pares de celdas euclidianas ilimitadas son reemplazadas en el plano proyectivo por celdas individuales que son cruzadas por la línea proyectiva en el infinito. ^[19]

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 las disposiciones 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 disposición proyectiva 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 prueba conocida del teorema de Sylvester-Gallai, de Melchior (1940), utiliza la característica de Euler para mostrar que dicho vértice siempre debe existir. ^[20]

Triángulos en arreglos

Un arreglo simplicial formado por 20 líneas, los lados y ejes de simetría de un decágono regular . Al sumar la línea en el infinito se obtiene otro arreglo simplicial con 21 líneas.

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

1. Un lápiz casi completo que consta de líneas que pasan por un único punto, junto con una única línea adicional que no pasa por el mismo punto, ${\displaystyle n-1}$
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 ejes de simetría de un polígono regular par, junto con la línea en el infinito.

Además, hay muchos otros ejemplos de arreglos simpliciales esporádicos que no encajan en ninguna familia infinita conocida. ^[22] Como escribe Branko Grünbaum , los arreglos simpliciales "aparecen como ejemplos o contraejemplos en muchos contextos de geometría combinatoria y sus aplicaciones". ^[23] Por ejemplo, Artés, Grünbaum y Llibre (1998) utilizan arreglos simpliciales para construir 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. Los dos contraejemplos conocidos de la conjetura de Dirac-Motzkin (que afirma que cualquier arreglo de líneas tiene al menos puntos ordinarios) son ambos simpliciales. ^[24] ${\displaystyle n}$ ${\displaystyle n/2}$

El gráfico 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 gráficos son cubos parciales , gráficos en los que los nodos pueden etiquetarse mediante vectores de bits de tal manera que la distancia del gráfico es 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. ^[25] Los gráficos duales de disposiciones simpliciales se han utilizado para construir familias infinitas de cubos parciales 3-regulares , isomorfos a los gráficos de zonoedros simples . ^[26]

También es de interés estudiar los números extremos de celdas triangulares en arreglos que no necesariamente pueden ser simpliciales. Cualquier arreglo en el plano proyectivo debe tener al menos triángulos. Cada arreglo que tenga solo triángulos debe ser simple. ^[27] Para arreglos euclidianos en lugar de proyectivos, el número mínimo de triángulos es , por el teorema del triángulo de Roberts . ^[28] Se sabe que el número máximo posible de caras triangulares en un arreglo simple está acotado superiormente por y acotado inferiormente por ; el límite inferior se logra mediante ciertos subconjuntos de las diagonales de un -gono regular. ^[29] Para arreglos no simples, el número máximo de triángulos es similar pero acotado más estrictamente. ^{[30] El} problema del triángulo de Kobon , estrechamente relacionado, solicita el número máximo de triángulos finitos no superpuestos en un arreglo en el plano euclidiano, sin contar las caras no acotadas que podrían formar triángulos en el plano proyectivo. Para algunos valores de , pero no todos , son posibles triángulos. ^[31] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle n(n-1)/3}$ ${\displaystyle n(n-3)/3}$ ${\displaystyle 2n}$ ${\displaystyle n}$ ${\displaystyle n(n-2)/3}$

Multicuadrículas y mosaicos de rombos

El gráfico dual de una disposición de líneas simple puede representarse geométricamente como una colección de rombos , uno por vértice de la disposición, con lados perpendiculares a las líneas que se encuentran en ese vértice. Estos rombos pueden unirse para formar un mosaico 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 a veces se conoce como diagrama de Klee , en honor a una publicación de Rudolf Klee en 1938 que utilizó esta técnica. Sin embargo, no todos los mosaicos de rombos provienen de líneas de esta manera. ^[32]

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

Existen también tres ordenaciones simpliciales infinitas formadas a partir de conjuntos de líneas paralelas. La teselación tetrakis cuadrada es una ordenación infinita de líneas que forman una teselación periódica que se asemeja a una multicuadrícula 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 ordenación es simplicial en lugar de simple. Su dual es la teselación cuadrada truncada . De manera similar, la teselación triangular es una ordenación simplicial infinita de líneas con tres familias paralelas, que tiene como dual la teselación hexagonal , y la teselación hexagonal bisectada es una ordenación simplicial infinita de líneas con seis familias paralelas y dos espaciamientos de línea, dual de la gran teselación 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 ordenaciones. ^[34]

Algoritmos

Construir un arreglo significa, dada como entrada una lista de las líneas en el arreglo, calcular una representación de los vértices, aristas y celdas del arreglo junto con las adyacencias entre estos objetos, por ejemplo como una lista de aristas doblemente conectadas . Debido al teorema de zona, los arreglos pueden construirse eficientemente mediante un algoritmo incremental que agrega una línea a la vez al arreglo de las líneas agregadas previamente: cada nueva línea puede agregarse en un tiempo proporcional a su zona, lo que resulta en un tiempo de construcción total de . ^[7] ${\displaystyle O(n^{2})}$ Sin embargo, los requisitos de memoria de este algoritmo son altos, por lo que puede ser más conveniente informar todas las características de un arreglo mediante un algoritmo que no mantenga todo el arreglo en la memoria a la vez. Esto nuevamente puede hacerse de manera eficiente, en tiempo ${\displaystyle O(n^{2})}$ y espacio , ${\displaystyle O(n)}$ mediante una técnica algorítmica conocida como barrido topológico . ^[35] Calcular un arreglo de líneas exactamente requiere una precisión numérica varias veces mayor que la de las coordenadas de entrada: si una línea se especifica por dos puntos en ella, las coordenadas de los vértices del arreglo 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 arreglos de manera eficiente con precisión numérica limitada. ^[36]

Además, los investigadores han estudiado algoritmos eficientes para construir porciones más pequeñas de un arreglo, como zonas, ^[37] -niveles, ^[38] o el conjunto de celdas que contienen un conjunto dado de puntos. ^[39] El problema de encontrar el vértice del arreglo con la coordenada mediana surge (en una forma dual) en las estadísticas robustas como el problema de calcular el estimador de Theil-Sen de un conjunto de puntos. ^[40] ${\displaystyle k}$ ${\displaystyle x}$

Marc van Kreveld sugirió el problema algorítmico de calcular los caminos más cortos entre los vértices de una disposición lineal, donde los caminos están restringidos a seguir los bordes 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 gráfico de la disposición. ^[41] Se conoce un algoritmo de aproximación , ^[42] y el problema se puede resolver de manera eficiente para líneas que caen en un pequeño número de familias paralelas (como es típico en las cuadrículas de calles urbanas), ^[43] pero el problema general permanece abierto.

Disposiciones de líneas no euclidianas

Una disposición pseudolineal es una familia de curvas que comparten propiedades topológicas similares con una disposición lineal. ^[44] Estas pueden definirse de manera más simple en el plano proyectivo como curvas cerradas simples , dos de las cuales se encuentran en un único punto de cruce. ^[45] Se dice que una disposición pseudolineal es extensible si es combinatoriamente equivalente a una disposición lineal. Determinar la extensibilidad es una tarea computacional difícil: es completo para la teoría existencial de los números reales distinguir las disposiciones extensibles de las no extensibles. ^[46] Toda disposición de un número finito de pseudolíneas puede extenderse de modo que se conviertan en líneas en una "extensió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. ^[47]

Otro tipo de geometría no euclidiana es el plano hiperbólico , y también se han estudiado los arreglos de líneas hiperbólicas en esta geometría. ^[48] 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 por 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 paralelas es una relación de equivalencia para líneas euclidianas pero no para líneas hiperbólicas. ^[49] El gráfico de intersección de las líneas en un arreglo hiperbólico puede ser un gráfico circular arbitrario . El concepto correspondiente a los arreglos de líneas hiperbólicas para pseudolíneas es un arreglo de pseudolínea débil , ^[50] una familia de curvas que tienen las mismas propiedades topológicas que las líneas ^[51] de modo que dos curvas cualesquiera en la familia se encuentran en un único punto de cruce o no tienen intersección. ^[50]

Véase también

• Configuración (geometría) , una disposición de líneas y un conjunto de puntos con todas las líneas que 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.
• Puente matemático , un puente en Cambridge, Inglaterra, cuyas vigas forman una disposición de líneas tangentes a su arco.

Notas

1. Grünbaum (1972), pág. 4.
2. Eppstein, Falmagne y Ovchinnikov (2007), págs. 177-178.
3. Ovchinnikov (2011), pág. 210.
4. Steiner (1826); Agarwal y Sharir (2000).
5. Halperin y Sharir (2018), pág. 724.
6. Sloane, N. J. A. (ed.), "Secuencia A000124 (Números poligonales centrales (la secuencia del Lazy Caterer))", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
7. Chazelle, Guibas y Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke y Seidel (1986).
8. Bern et al. (1991); un manuscrito inédito de Rom Pinchasi de 2011 afirma que el límite es ligeramente más fuerte . ${\displaystyle \lfloor 9.5n\rfloor -3}$
9. Berna y otros (1991).
10. Aronov, Matoušek y Sharir (1994).
11. Dey (1998); Tóth (2001). El problema de limitar la complejidad de los k -niveles fue estudiado por primera vez por Lovász (1971) y Erdős et al. (1973).
12. Alon y Győri (1986).
13. Balogh y col. (2004); véase también Matoušek (1991).
14. Canham (1969); Clarkson y otros (1990).
15. Ajtai y otros. (1982); Leighton (1983).
16. Székely (1997).
17. Goodman & Pollack (1993), p. 109 Archivado el 1 de enero de 2023 en Wayback Machine : "El escenario natural para los arreglos de líneas es el plano proyectivo real"
18. Polster (1998), pág. 223.
19. Goodman y Pollack (1993), pág. 110.
20. Esta es la prueba más antigua citada por Borwein y Moser (1990), pero escriben que la misma prueba probablemente fue dada "mucho antes por otros".
21. Melchor (1940); Grünbaum (2009).
22. Grünbaum (1972); Grünbaum (2009).
23. Grünbaum (2009).
24. Crowe y McKee (1968); Dirac (1951); Kelly y Moser (1958); Grünbaum (1972), página 18.
25. Eppstein, Falmagne y Ovchinnikov (2007), pág. 180.
26. Eppstein (2006).
27. Grünbaum (1972); Levi (1926); Roudneff (1988).
28. Grünbaum (1972).
29. Füredi y Palasti (1984); Grünbaum (1972).
30. Purdy (1979); Purdy (1980);
31. Moreno y Prieto-Martínez (2021).
32. Klee (1938).
33. de Bruijn (1981).
34. Abramenko y Brown (2008).
35. Edelsbrunner y Guibas (1989).
36. Fortune y Milenkovic (1991); Greene y Yao (1986); Milenkovic (1989).
37. Aharoni y otros (1999).
38. Agarwal y col. (1998); Chan (1999); Cole, Sharir y Yap (1987); Edelsbrunner y Welzl (1986).
39. Agarwal (1990); Agarwal, Matoušek y Sharir (1998); Edelsbrunner, Guibas y Sharir (1990).
40. Cole y otros (1989).
41. Erickson (1997).
42. Bose y otros (1996).
43. Eppstein y Hart (1999).
44. Grünbaum (1972); Agarwal y Sharir (2002).
45. Esta definición es de Grünbaum (1972). Para una comparación de definiciones alternativas de pseudolíneas, véase Eppstein, Falmagne y Ovchinnikov (2007).
46. Shor (1991); Schaefer (2010).
47. Goodman y otros (1994).
48. Vestido, Koolen y Moulton (2002).
49. Martín (1996), págs. 41, 338.
50. de Fraysseix y Ossona de Méndez (2003).
51. Aquí es apropiada una definición alternativa de Shor (1991), según la cual una pseudolínea es la imagen de una línea bajo un homeomorfismo del plano.

Referencias

• Abramenko, Peter; Brown, Kenneth S. (2008), Edificios: teoría y aplicaciones , Textos de posgrado en matemáticas, vol. 248, Nueva York: Springer, doi : 10.1007/978-0-387-78835-7, ISBN 978-0-387-78834-0, Sr.  2439729; véase el ejemplo 10.14, págs. 519-520
• Agarwal, PK (1990), "Disposiciones de partición de líneas II: Aplicaciones", Geometría discreta y computacional , 5 (1): 533–573, doi : 10.1007/BF02187809
• Agarwal, PK ; de Berg, M. ; Matoušek, J. ; Schwarzkopf, O. (1998), "Construcción de niveles en arreglos y diagramas de Voronoi de orden superior", SIAM Journal on Computing , 27 (3): 654–667, CiteSeerX  10.1.1.51.5064 , doi :10.1137/S0097539795281840
• Agarwal, PK ; Matoušek, J .; Sharir, M. (1998), "Cálculo de muchas caras en disposiciones de líneas y segmentos", SIAM Journal on Computing , 27 (2): 491–505, doi :10.1137/S009753979426616X, hdl : 1874/17088
• Agarwal, PK ; Sharir, M. (2000), "Arrangements and their applications" (PDF) , en Sack, J.-R. ; Urrutia, J. (eds.), Handbook of Computational Geometry , Elsevier, pp. 49–119, archivado (PDF) desde el original el 2021-04-11 , consultado el 2018-11-11
• Agarwal, PK ; Sharir, M. (2002), "Disposiciones pseudolineales: dualidad, algoritmos y aplicaciones", Proc. 13.° Simposio ACM-SIAM sobre algoritmos discretos (SODA '02) , San Francisco: Society for Industrial and Applied Mathematics, págs. 800–809
• Ageev, AA (1996), "Un gráfico circular sin triángulos con número cromático 5", Discrete Mathematics , 152 (1–3): 295–298, doi : 10.1016/0012-365X(95)00349-2
• Aharoni, Y.; Halperin, D.; Hanniel, I.; Har-Peled, S .; Linhart, C. (1999), "Construcción de zonas en línea en arreglos de líneas en el plano", en Vitter, Jeffrey S.; Zaroliagis, Christos D. (eds.), Algorithm Engineering: 3rd International Workshop, WAE'99, Londres, Reino Unido, 19-21 de julio de 1999, Actas , Lecture Notes in Computer Science, vol. 1668, Springer-Verlag, págs. 139-153, CiteSeerX  10.1.1.35.7681 , doi :10.1007/3-540-48318-7_13, ISBN 978-3-540-66427-7
• Ajtai, M. ; Chvátal, V. ; Newborn, M. ; Szemerédi, E. (1982), "Subgrafos sin cruces", Teoría y práctica de la combinatoria , Estudios matemáticos de Holanda Septentrional, vol. 60, Holanda Septentrional, págs. 9-12, MR  0806962
• Alon, N. ; Győri, E. (1986), "El número de semiespacios pequeños de un conjunto finito de puntos en el plano", Journal of Combinatorial Theory, Serie A , 41 : 154–157, doi : 10.1016/0097-3165(86)90122-6
• Aronov, B. ; Matoušek, J. ; Sharir, M. (1994), "Sobre la suma de cuadrados de complejidades celulares en disposiciones de hiperplanos", Journal of Combinatorial Theory, Serie A , 65 (2): 311–321, doi : 10.1016/0097-3165(94)90027-2
• Artés, JC; Grünbaum, B .; Llibre, J. (1998), "Sobre el número de líneas rectas invariantes para sistemas diferenciales polinomiales" (PDF) , Pacific Journal of Mathematics , 184 (2): 207–230, doi : 10.2140/pjm.1998.184.207 , archivado (PDF) desde el original el 2010-07-18 , consultado el 2008-12-15
• Balogh, J.; Regev, O.; Smyth, C.; Steiger, W.; Szegedy, M. (2004), "Trayectorias monótonas largas en arreglos lineales", Geometría discreta y computacional , 32 (2): 167–176, doi : 10.1007/s00454-004-1119-1
• Bern, MW; Eppstein, D .; Plassman, PE; Yao, FF (1991), "Teoremas del horizonte para líneas y polígonos", en Goodman, JE ; Pollack, R.; Steiger, W. (eds.), Geometría discreta y computacional: artículos del año especial de DIMACS , DIMACS Ser. Discrete Math. and Theoretical Computer Science (6.ª ed.), Amer. Math. Soc., págs. 45–66, MR  1143288
• Borwein, P. ; Moser, WOJ (1990), "Un estudio del problema de Sylvester y sus generalizaciones", Aequationes Mathematicae , 40 (1): 111–135, doi :10.1007/BF02112289, MR  1069788, S2CID  122052678
• Bose, P .; Evans, W.; Kirkpatrick, DG ; McAllister, M.; Snoeyink, J. (1996), "Aproximación de los caminos más cortos en arreglos de líneas", Proc. 8th Canadian Conf. Computational Geometry , págs. 143–148
• de Bruijn, NG (1981), "Teoría algebraica de las teselas no periódicas del plano de Penrose" (PDF) , Indagationes Mathematicae , 43 : 38–66, archivado (PDF) desde el original el 2021-05-07 , consultado el 2008-12-14
• Canham, RJ (1969), "Un teorema sobre disposiciones de líneas en el plano", Israel Journal of Mathematics , 7 (4): 393–397, doi : 10.1007/BF02788872 , S2CID  123541779
• Chan, T. (1999), Observaciones sobre algoritmos de nivel k en el plano, archivado desde el original el 4 de noviembre de 2010
• Chazelle, B. ; Guibas, LJ ; Lee, DT (1985), "El poder de la dualidad geométrica", BIT Numerical Mathematics , 25 (1): 76–90, doi :10.1007/BF01934990, S2CID  122411548
• Clarkson, K. ; Edelsbrunner, H. ; Guibas, LJ ; Sharir, M. ; Welzl, E. (1990), "Límites de complejidad combinatoria para arreglos de curvas y esferas", Geometría discreta y computacional , 5 (1): 99–160, doi : 10.1007/BF02187783
• Cole, Richard; Salowe, Jeffrey S.; Steiger, WL; Szemerédi, Endre (1989), "Un algoritmo de tiempo óptimo para la selección de pendientes", SIAM Journal on Computing , 18 (4): 792–810, doi :10.1137/0218055, MR  1004799
• Cole, R.; Sharir, M .; Yap, C.-K. (1987), "Sobre los k -hulls y problemas relacionados", SIAM Journal on Computing , 16 (1): 61–77, doi :10.1137/0216005
• Crowe, DW; McKee, TA (1968), "El problema de Sylvester en puntos colineales", Mathematics Magazine , 41 (1): 30–34, doi :10.2307/2687957, JSTOR  2687957
• Dey, TL (1998), "Límites mejorados para conjuntos k planares y problemas relacionados", Geometría discreta y computacional , 19 (3): 373–382, doi : 10.1007/PL00009354 , MR  1608878
• Dirac, G. (1951), "Propiedades de colinealidad de conjuntos de puntos", Quarterly Journal of Mathematics , 2 (1): 221–227, Bibcode :1951QJMat...2..221D, doi :10.1093/qmath/2.1.221
• Dress, A.; Koolen, JH; Moulton, V. (2002), "Disposiciones en línea en el plano hiperbólico", European Journal of Combinatorics , 23 (5): 549–557, doi : 10.1006/eujc.2002.0582 , MR  1931939
• Edelsbrunner, H. (1987), Algoritmos en geometría combinatoria , Monografías EATCS en informática teórica, Springer-Verlag, ISBN 978-3-540-13722-1
• Edelsbrunner, H. ; Guibas, LJ (1989), "Barrido topológico de un arreglo", Journal of Computer and System Sciences , 38 (1): 165–194, doi : 10.1016/0022-0000(89)90038-X
• Edelsbrunner, H. ; Guibas, LJ ; Sharir, M. (1990), "La complejidad y construcción de muchas caras en arreglos de líneas y segmentos", Geometría discreta y computacional , 5 (1): 161–196, doi : 10.1007/BF02187784
• Edelsbrunner, H. ; O'Rourke, J. ; Seidel, R. (1986), "Construcción de arreglos de líneas e hiperplanos con aplicaciones", SIAM Journal on Computing , 15 (2): 341–363, doi :10.1137/0215024
• Edelsbrunner, H. ; Welzl, E. (1986), "Construcción de cinturones en disposiciones bidimensionales con aplicaciones", SIAM Journal on Computing , 15 (1): 271–284, doi :10.1137/0215019
• Eppstein, D. (2006), "Cubos parciales cúbicos a partir de arreglos simpliciales", Electronic Journal of Combinatorics , 13 (1, R79): 1–14, arXiv : math.CO/0510263 , doi :10.37236/1105, MR  2255421, S2CID  8608953, archivado desde el original el 2012-02-14 , consultado el 2008-12-14
• Eppstein, D .; Falmagne, J.-Cl. ; Ovchinnikov, S. (2007), Teoría de los medios , Springer-Verlag
• Eppstein, D.; Hart, D. (1999), "Caminos más cortos en una disposición con orientaciones de línea k", Actas del 10º Simposio ACM–SIAM sobre Algoritmos Discretos (SODA '99) , págs. 310–316
• Erdős, P .; Lovász, L .; Simmons, A.; Straus, EG (1973), "Gráficos de disección de conjuntos de puntos planos", A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) , Ámsterdam: Holanda Septentrional, págs. 139-149, MR  0363986
• Erickson, J. (1997), Caminos más cortos en arreglos lineales, archivado desde el original el 2008-12-03 , consultado el 2008-12-15
• Fortune, S.; Milenkovic, V. (1991), "Estabilidad numérica de algoritmos para arreglos de líneas", Proc. 7th ACM Symposium on Computational Geometry (SoCG '91) , págs. 334–341, CiteSeerX  10.1.1.56.2404 , doi :10.1145/109648.109685, ISBN 978-0897914260, Número de identificación del sujeto  2861855
• de Fraysseix, H.; Ossona de Mendez, P. (2003), "Estiramiento de sistemas de contacto de arco de Jordan", Actas del 11.° Simposio Internacional sobre Dibujo de Gráficos (GD 2003) , Lecture Notes in Computer Science (2912 ed.), Springer-Verlag, págs. 71–85
• Füredi, Z. ; Palásti, I. (1984), "Disposiciones de líneas con un gran número de triángulos" (PDF) , Proceedings of the American Mathematical Society , 92 (4): 561–566, doi :10.2307/2045427, JSTOR  2045427, archivado (PDF) desde el original el 2016-03-03 , consultado el 2008-12-15
• Goodman, Jacob E. ; Pollack, Richard (1993), "Secuencias permisibles y tipos de orden en geometría discreta y computacional", en Pach, János (ed.), Nuevas tendencias en geometría discreta y computacional , Algorithms and Combinatorics, vol. 10, Berlín: Springer, págs. 103–134, doi :10.1007/978-3-642-58043-7_6, MR  1228041
• Goodman, Jacob E .; Pollack, Richard ; Wenger, Rephael; Zamfirescu, Tudor (1994), "Cada disposición se extiende a una extensión", Combinatorica , 14 (3): 301–306, doi :10.1007/BF01212978, MR  1305899, S2CID  42055590
• Greene, D.; Yao, FF (1986), "Geometría computacional de resolución finita", Actas del 27.º Simposio IEEE sobre Fundamentos de la informática (FOCS '86) , págs. 143-152, doi :10.1109/SFCS.1986.19, ISBN 978-0-8186-0740-0, Número de identificación del sujeto  2624319
• Grünbaum, B. (1972), Arreglos y distribuciones , Serie de conferencias regionales sobre matemáticas, vol. 10, Providence, RI: American Mathematical Society
• Grünbaum, B. (1974), Notas sobre arreglos , Universidad de Washington, hdl :1773/15699; ver pág. 6 de "Disposiciones euclidianas" (pág. 101 del pdf vinculado)
• Grünbaum, Branko (2009), "Un catálogo de arreglos simpliciales en el plano proyectivo real", Ars Mathematica Contemporanea , 2 (1): 1–25, doi : 10.26493/1855-3974.88.e12 , hdl : 1773/2269 , MR  2485643
• Halperin, D.; Sharir, M. (2018), "Arreglos", en Goodman, Jacob E.; O'Rourke, Joseph; Tóth, Csaba D. (eds.), Manual de geometría discreta y computacional , Matemáticas discretas y sus aplicaciones (3.ª ed.), Boca Raton, Florida: CRC Press, págs. 723–762, ISBN 978-1-4987-1139-5, Sr.  3793131
• Kelly, LM ; Moser, WOJ (1958), "Sobre el número de líneas ordinarias determinadas por n puntos", Revista Canadiense de Matemáticas , 10 : 210–219, doi : 10.4153/CJM-1958-024-6
• Klee, R. (1938), Über die einfachen Konfigurationen der euklidischen und der projektiven Ebene , Dresde: Focken & Oltmanns
• Leighton, FT (1983), Problemas de complejidad en VLSI , Foundations of Computing Series, Cambridge, MA: MIT Press
• Levi, F. (1926), "Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade", Ber. Matemáticas-Física. kl. Sächs. Akád. Wiss. Leipzig , 78 : 256–267
• Lovász, L. (1971), "Sobre el número de líneas de reducción a la mitad", Annales Universitatis Scientiarum Budapestinensis de Rolando Eőtvős Nominatae Sectio Mathematica , 14 : 107–108
• Martin, George E. (1996), Los fundamentos de la geometría y el plano no euclidiano , Textos de pregrado en matemáticas, Springer-Verlag, ISBN 0-387-90694-0, Sr.  1410263
• Matoušek, J. (1991), "Límites inferiores de la longitud de las trayectorias monótonas en los arreglos", Geometría discreta y computacional , 6 (1): 129–134, doi : 10.1007/BF02574679
• Melchior, E. (1940), "Über Vielseite der projektiven Ebene", Deutsche Mathematik , 5 : 461–475
• Milenkovic, V. (1989), "Geometría de doble precisión: una técnica general para calcular intersecciones de líneas y segmentos utilizando aritmética redondeada", Actas del 30.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (FOCS '89) , págs. 500-505, doi :10.1109/SFCS.1989.63525, ISBN 978-0-8186-1982-3, S2CID18564700 ​
• Moreno, José Pedro; Prieto-Martínez, Luis Felipe (2021), "El problema de los triángulos de Kobon", La Gaceta de la Real Sociedad Matemática Española (en español), 24 (1): 111–130, hdl : 10486/705416, SEÑOR  4225268
• Motzkin, Th. (1951), "Las líneas y los planos que conectan los puntos de un conjunto finito", Transactions of the American Mathematical Society , 70 (3): 451–464, doi : 10.2307/1990609 , JSTOR  1990609
• Ovchinnikov, Sergei (2011), Gráficos y cubos , Universitext, Nueva York: Springer, doi :10.1007/978-1-4614-0797-3, ISBN 978-1-4614-0796-6, Sr.  3014880
• Polster, Burkard (1998), Un libro ilustrado geométrico , Universitext, Springer-Verlag, Nueva York, doi :10.1007/978-1-4419-8526-2, ISBN 0-387-98437-2, Sr.  1640615
• Purdy, GB (1979), "Triángulos en disposiciones de líneas", Matemáticas discretas , 25 (2): 157–163, doi : 10.1016/0012-365X(79)90018-9
• Purdy, GB (1980), "Triángulos en disposiciones de líneas, II", Actas de la American Mathematical Society , 79 : 77–81, doi : 10.1090/S0002-9939-1980-0560588-4
• Roudneff, J.-P. (1988), "Los arreglos de líneas con un número mínimo de triángulos son simples", Geometría discreta y computacional , 3 (1): 97–102, doi : 10.1007/BF02187900
• Schaefer, Marcus (2010), "Complejidad de algunos problemas geométricos y topológicos" (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, Documentos revisados ​​, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, págs. 334–344, doi : 10.1007/978-3-642-11805-0_32 , ISBN 978-3-642-11804-3, archivado (PDF) del original el 26 de junio de 2021 , consultado el 25 de febrero de 2011
• Shor, PW (1991), "La capacidad de estiramiento de las pseudolíneas es NP-dura", en Gritzmann, P.; Sturmfels, B. (eds.), Geometría aplicada y matemáticas discretas: la publicación Victor Klee Festschrift , Serie DIMACS en matemáticas discretas y ciencias de la computación teóricas, vol. 4, Providence, RI: American Mathematical Society, págs. 531–554
• Steiner, J. (1826), "Einige Gesetze über die Theilung der Ebene und des Raumes", J. Reine Angew. Matemáticas. , 1 : 349–364, doi : 10.1515/crll.1826.1.349, S2CID  120477563
• Strommer, TO (1977), "Triángulos en arreglos de líneas", Journal of Combinatorial Theory, Serie A , 23 (3): 314–320, doi : 10.1016/0097-3165(77)90022-X
• Székely, LA (1997), "Números cruzados y problemas de Erdős difíciles en geometría discreta" (PDF) , Combinatorics, Probability and Computing , 6 (3): 353–358, doi :10.1017/S0963548397002976, S2CID  36602807, archivado (PDF) del original el 2017-08-08 , recuperado 2019-09-23
• Tóth, G. (2001), "Conjuntos de puntos con muchos k -conjuntos", Geometría discreta y computacional , 26 (2): 187–194, doi : 10.1007/s004540010022

Enlaces externos

• Base de datos de disposiciones lineales combinatoriamente diferentes