Disposición de líneas

Subdivisión del plano por líneas.

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

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

Definición

Intuitivamente, cualquier conjunto finito de líneas en el plano corta el plano en polígonos (celdas) bidimensionales, segmentos de línea o rayos unidimensionales 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 encuentran. 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 propia línea. Se pueden considerar dos puntos equivalentes si tienen la misma clasificación respecto de 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 tres tipos siguientes:

1. Las celdas o cámaras de la disposición son regiones bidimensionales que no forman parte de ninguna línea. Forman el interior de polígonos convexos acotados o regiones convexas ilimitadas. 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 del arreglo son regiones unidimensionales que pertenecen 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 los componentes conectados de sus puntos no cortados.
3. Los vértices del arreglo son puntos aislados que pertenecen a dos o más líneas, donde esas 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 recta). El sistema de objetos de los tres tipos, unidos por este operador de frontera, forma un complejo de células que cubre el plano. Se dice que dos disposiciones son isomorfas o combinatoriamente equivalentes si existe una correspondencia uno a uno que preserva los límites entre los objetos en sus complejos celulares asociados. ^[1]

La misma clasificación de puntos y las mismas formas de clases de equivalencia se pueden utilizar para disposiciones infinitas pero localmente finitas , en las que cada subconjunto acotado del plano puede ser atravesado sólo por un número finito de líneas, ^[2] aunque en este caso el conjunto ilimitado Las células pueden tener infinitos lados. ^[3]

Complejidad de los arreglos

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

• Un arreglo 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 arreglos simples , aquellos en los que cada dos líneas se cruzan en un vértice que está separado 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 están cruzados por más de dos líneas. ^[5] ${\displaystyle n}$ ${\displaystyle n(n-1)/2}$
• Cualquier disposición se puede rotar 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 infinitos rayos hacia abajo, uno por línea. Estos rayos separan las células de la disposición que no están limitadas en dirección descendente. Todas las celdas restantes tienen un vértice inferior único (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 . Sumando las celdas ilimitadas y acotadas, 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 catering perezoso . ^[6] ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle n(n-1)/2}$ ${\displaystyle n(n+1)/2+1}$
• El número de aristas de la disposición es como máximo , ${\displaystyle n^{2}}$ como se puede ver usando la característica de Euler para calcularlo a partir del número de vértices y celdas, o observando que cada línea está dividida en como máximo aristas por las otras líneas. Nuevamente, este límite del peor de los casos 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 el conjunto 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 bordes 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 bordes de las celdas que pertenecen a ambos lados es ${\displaystyle \ell }$ 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 intersecadas por cualquier curva convexa es , ${\displaystyle O(n\alpha (n))}$ donde denota la función inversa de Ackermann , como se puede mostrar usando 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 una disposición es la cadena poligonal formada por los bordes que tienen exactamente otras líneas directamente debajo de ellos. El nivel es la parte 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] Por el contrario, 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 aristas que intersecta 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 delimitada por todas las líneas, en general no es posible que diferentes celdas estén todas limitadas por líneas. Más bien, la complejidad total de las células es , como máximo , ^[14] casi el mismo límite que ocurre en el teorema de Szemerédi-Trotter sobre las incidencias de las líneas de puntos en el plano. Una prueba simple de esto se deduce de la desigualdad del número de cruce : ^[15] si las celdas tienen un total de aristas, se puede formar un gráfico con nodos (uno por celda) y aristas (una por par de celdas consecutivas en la misma línea). Los bordes 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 tanto, hay cruces en este dibujo. Sin embargo, por la desigualdad del número de cruce, hay cruces. Para satisfacer ambos límites, debe ser . ^[dieciséis] ${\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})}$

Arreglos proyectivos y dualidad proyectiva.

A menudo es conveniente estudiar la disposición de las líneas no en el plano euclidiano sino en el plano proyectivo , debido al hecho de que en geometría proyectiva cada par de líneas tiene un punto de intersección. ^[17] En el plano proyectivo, no es posible definir disposiciones utilizando lados de líneas, porque una línea en el plano proyectivo no separa el plano en dos lados distintos. ^[18] Sin embargo, aún se pueden definir las celdas de una disposición como los componentes conectados de los puntos que no pertenecen a ninguna línea, los bordes como los componentes conectados de conjuntos de puntos que pertenecen a una sola línea y los vértices como 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 son reemplazados por un solo borde 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 Las células euclidianas ilimitadas se reemplazan en el plano proyectivo por células individuales que son atravesadas por la línea proyectiva en el infinito. ^[19]

Debido a la dualidad proyectiva , muchas afirmaciones sobre las propiedades combinatorias de puntos en el plano pueden entenderse más fácilmente en una forma dual equivalente sobre la disposición 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 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 sólo se cruzan dos rectas. La prueba más antigua conocida del teorema de Sylvester-Gallai, realizada por Melchior (1940), utiliza la característica de Euler para demostrar que dicho vértice siempre debe existir. ^[20]

Triangulos en arreglos

Un arreglo simple formado por 20 rectas, los lados y ejes de simetría de un decágono regular . Agregar la línea en el infinito produce otra disposición simple 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. Melchor estudió por primera vez los arreglos simples. ^[21] Se conocen tres familias infinitas de disposiciones de líneas simpliciales:

1. Un casi lápiz que consta de líneas que pasan por un solo punto, junto con una única línea adicional que no pasa por el mismo punto, ${\displaystyle n-1}$
2. La familia de rectas formada 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 recta del 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 de una conjetura sobre la relación entre el grado de un conjunto de ecuaciones diferenciales y el número de rectas invariantes que pueden tener las ecuaciones. Los dos contraejemplos conocidos de la conjetura de Dirac-Motzkin (que establece que cualquier disposición de líneas tiene al menos puntos ordinarios) son simpliciales. ^[24] ${\displaystyle n}$ ${\displaystyle n/2}$

El gráfico dual de una disposición lineal tiene un nodo por celda y un borde que une cualquier par de celdas que comparten un borde 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 sea igual a la distancia de Hamming entre etiquetas. En el caso de una disposición de líneas, 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] Se han utilizado gráficas duales de arreglos simpliciales para construir familias infinitas de cubos parciales de 3 regulares , isomórficos a las gráficas de zonoedros simples . ^[26]

También es interesante estudiar los números extremos de celdas triangulares en disposiciones que no necesariamente pueden ser simples. Cualquier disposición en el plano proyectivo debe tener al menos triángulos. Todo arreglo que tenga sólo triángulos debe ser simple. ^[27] Para disposiciones euclidianas en lugar de proyectivas, el número mínimo de triángulos es , según el teorema del triángulo de Roberts . ^[28] Se sabe que el número máximo posible de caras triangulares en una disposición simple está acotado superior por y acotado inferior por ; el límite inferior se logra mediante ciertos subconjuntos de las diagonales de un -gón regular. ^[29] Para disposiciones no simples, el número máximo de triángulos es similar pero está más estrechamente delimitado. ^[30] 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 ilimitadas que podrían formar triángulos en el plano proyectivo. Para algunos valores de , pero no para todos, los triángulos son posibles. ^[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}$

Rejillas múltiples y mosaicos de rombos

La gráfica dual de una disposición lineal simple se puede representar geométricamente como una colección de rombos , uno por vértice de la disposición, con lados perpendiculares a las rectas 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 finito de líneas. Esta construcción se conoce a veces como diagrama de Klee , en honor a una publicación de Rudolf Klee en 1938 que utilizaba 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 líneas consta de conjuntos de líneas paralelas equiespaciadas. Para dos familias perpendiculares de líneas paralelas, esta construcción solo proporciona el conocido mosaico cuadrado del plano, y para tres familias de líneas en ángulos de 120 grados entre sí (formando un mosaico trihexagonal ), esto produce el mosaico de rombos . 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 pentágrida ) produce una familia de mosaicos que incluyen la versión rómbica de los mosaicos de Penrose . ^[33] ${\displaystyle k}$

También existen tres arreglos simpliciales infinitos formados a partir de conjuntos de líneas paralelas. El mosaico cuadrado de tetrakis es una disposición infinita de líneas que forman un mosaico periódico que se asemeja a una red múltiple con cuatro familias paralelas, pero en el que dos de las familias están más espaciadas que las otras dos, y en el que la disposición es más simple que simple. Su dual es el mosaico cuadrado truncado . De manera similar, el mosaico triangular es un arreglo de líneas simplicial infinita con tres familias paralelas, que tiene como dual el mosaico hexagonal , y el mosaico hexagonal bisecado es un arreglo de líneas simplicial infinita con seis familias paralelas y dos espacios entre líneas, dual al gran rombitrihexagonal. mosaico . 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 estos arreglos. ^[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 la zona, los arreglos se pueden construir 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 se puede agregar en un tiempo proporcional a su zona, lo que resulta en un tiempo total de construcción. 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 también se puede hacer de manera eficiente, en el tiempo ${\displaystyle O(n^{2})}$ y el espacio , ${\displaystyle O(n)}$ mediante una técnica algorítmica conocida como barrido topológico . ^[35] Calcular exactamente una disposición de líneas requiere una precisión numérica varias veces mayor que la de las coordenadas de entrada: si una línea está especificada por dos puntos, 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 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 una disposición, como zonas, ^[37] niveles, ^[38] o el conjunto de celdas que contienen un conjunto determinado de puntos. ^[39] El problema de encontrar el vértice de disposición con la coordenada mediana surge (de forma dual) en estadística robusta 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 en 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 ruta más corta al conjunto. gráfico de disposición. ^[41] Se conoce un algoritmo de aproximación , ^[42] y el problema puede resolverse eficientemente para líneas que caen en un pequeño número de familias paralelas (como es típico en las redes de calles urbanas), ^[43] pero el problema general permanece abierto.

Disposiciones de líneas no euclidianas

Una disposición de pseudolínea es una familia de curvas que comparten propiedades topológicas similares con una disposición de línea. ^[44] Estos pueden definirse de manera más simple en el plano proyectivo como curvas cerradas simples de las cuales dos de ellas se encuentran en un solo punto de cruce. ^[45] Se dice que una disposición pseudolínea es extensible si es combinatoriamente equivalente a una disposición lineal. Determinar la extensibilidad es una tarea computacional difícil: para la teoría existencial de los reales es completo distinguir las disposiciones estirables de las no estirables. ^{[46] Cada disposición de un número finito de pseudolíneas se puede extender para 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 línea única (como en el Plano euclidiano) pero en el 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 las disposiciones de las líneas hiperbólicas en esta geometría. ^[48] ​​Cualquier conjunto finito de líneas en el plano euclidiano tiene una disposición combinatoria equivalente en el plano hiperbólico (por ejemplo, encerrando los vértices de la disposición 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 las disposiciones de líneas hiperbólicas que en el plano euclidiano: en particular, la relación de ser paralelos es una relación de equivalencia para las líneas euclidianas pero no para las líneas hiperbólicas. ^[49] La gráfica de intersección de las líneas en una disposición hiperbólica puede ser una gráfica circular arbitraria . El concepto correspondiente a las disposiciones de líneas hiperbólicas para pseudolíneas es una disposición de pseudolíneas 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 de la familia se encuentran en un solo punto de cruce o no tienen intersección. ^[50]

Ver también

• 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 de 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 un arreglo 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.), "Sequence A000124 (Números poligonales centrales (la secuencia de Lazy Caterer))", La enciclopedia en línea de secuencias enteras , Fundación OEIS
7. Chazelle, Guibas y Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke y Seidel (1986).
8. Berna y col. (1991); un manuscrito inédito de Rom Pinchasi de 2011 afirma tener una encuadernación ligeramente más fuerte . ${\displaystyle \lfloor 9.5n\rfloor -3}$
9. Berna y col. (1991).
10. Aronov, Matoušek y Sharir (1994).
11. Dey (1998); Toth (2001). El problema de delimitar la complejidad de 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 cols. (1990).
15. Ajtai y otros. (mil novecientos ochenta y dos); Leighton (1983).
16. Székely (1997).
17. Goodman y Pollack (1993), pág. 109 Archivado el 1 de enero de 2023 en Wayback Machine : "El entorno natural para la disposición 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 probablemente otros dieron la misma prueba "mucho antes".
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); Leví (1926); Roudneff (1988).
28. Grünbaum (1972).
29. Füredi y Palasti (1984); Grünbaum (1972).
30. Purdy (1979); Purdy (1980); Strommer (1977).
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. Fortuna y Milenkovic (1991); Greene y Yao (1986); Milenkovic (1989).
37. Aharoni y col. (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 col. (1989).
41. Erickson (1997).
42. Bosé y col. (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, consulte Eppstein, Falmagne y Ovchinnikov (2007).
46. Corto (1991); Schäfer (2010).
47. Goodman y col. (1994).
48. Vestido, Koolen & 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), de que una pseudolínea es la imagen de una línea bajo un homeomorfismo del plano.

Referencias

• Abramenko, Pedro; 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, señor  2439729; consulte el ejemplo 10.14, págs. 519–520
• Agarwal, PK (1990), "Disposiciones de partición de líneas II: aplicaciones", Geometría computacional y discreta , 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), "Calcular 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), "Arreglos y sus aplicaciones" (PDF) , en Sack, J.-R. ; Urrutia, J. (eds.), Handbook of Computational Geometry , Elsevier, págs. 49-119, archivado (PDF) desde el original el 11 de abril de 2021 , consultado el 11 de noviembre de 2018.
• Agarwal, PK ; Sharir, M. (2002), "Disposiciones de pseudolíneas: dualidad, algoritmos y aplicaciones", Proc. 13.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '02) , San Francisco: Sociedad de Matemáticas Industriales y Aplicadas, págs.
• Ageev, AA (1996), "Un gráfico circular sin triángulos con el número cromático 5", Matemáticas discretas , 152 (1–3): 295–298, doi : 10.1016/0012-365X(95)00349-2
• Aharoni, Y.; Halperin, D.; Hanniel, yo; Har-Peled, S .; Linhart, C. (1999), "Construcción de zonas en línea en disposiciones de líneas en el plano", en Vitter, Jeffrey S .; Zaroliagis, Christos D. (eds.), Ingeniería de algoritmos: tercer taller internacional, WAE'99, Londres, Reino Unido, 19 al 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 .; Recién nacido, M. ; Szemerédi, E. (1982), "Subgrafos sin cruce", Teoría y práctica de la combinatoria , Estudios de matemáticas de Holanda Septentrional, vol. 60, Holanda Septentrional, págs. 9-12, SEÑOR  0806962
• Alón, N .; Győri, E. (1986), "El número de pequeños semiespacios 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 hiperplano", 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 rectas invariantes para sistemas diferenciales polinomiales" (PDF) , Pacific Journal of Mathematics , 184 (2): 207–230, doi : 10.2140/pjm.1998.184.207 , archivado (PDF) del original el 18 de julio de 2010 , consultado el 15 de diciembre de 2008
• Balogh, J.; Regev, O.; Smith, C.; Steiger, W.; Szegedy, M. (2004), "Trayectorias largas y monótonas en disposiciones lineales", Geometría computacional y discreta , 32 (2): 167–176, doi : 10.1007/s00454-004-1119-1
• Berna, 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 DIMACS , DIMACS Ser. Matemáticas discretas. y Ciencias de la Computación Teórica (6 ed.), Amer. Matemáticas. Soc., págs. 45–66, SEÑOR  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
• Bosé, P .; Evans, W.; Kirkpatrick, director general ; McAllister, M.; Snoeyink, J. (1996), "Aproximación de caminos más cortos en disposiciones de líneas", Proc. 8ª Conferencia Canadiense. Geometría computacional , págs. 143-148
• de Bruijn, NG (1981), "Teoría algebraica de los mosaicos no periódicos del plano de Penrose" (PDF) , Indagationes Mathematicae , 43 : 38–66, archivado (PDF) desde el original el 7 de mayo de 2021 , recuperado en 2008 -12-14
• Canham, RJ (1969), "Un teorema sobre la disposición de líneas en el plano", Israel Journal of Mathematics , 7 (4): 393–397, doi : 10.1007/BF02788872 , S2CID  123541779
• Chan, T. (1999), Comentarios 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 disposiciones de curvas y esferas", Geometría computacional y discreta , 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 .; Sí, C.-K. (1987), "Sobre k -cascos y problemas relacionados", Revista SIAM de Computación , 16 (1): 61–77, doi :10.1137/0216005
• Crowe, DW; McKee, TA (1968), "El problema de Sylvester sobre puntos colineales", Mathematics Magazine , 41 (1): 30–34, doi :10.2307/2687957, JSTOR  2687957
• Dey, TL (1998), "Límites mejorados para conjuntos k planos 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
• Vestido, 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), "Un arreglo de barrido topológico", 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 disposiciones 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 disposiciones 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 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 14 de febrero de 2012 , consultado el 14 de diciembre de 2008
• Eppstein, D .; Falmagne, J.-Cl. ; Ovchinnikov, S. (2007), Teoría de los medios , Springer-Verlag
• Eppstein, D .; Hart, D. (1999), "Los caminos más cortos en un arreglo con k orientaciones de líneas", Actas del décimo simposio ACM-SIAM sobre algoritmos discretos (SODA '99) , págs.
• 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, Colorado, 1971) , Ámsterdam: Holanda Septentrional, págs. 139–149, SEÑOR  0363986.
• Erickson, J. (1997), Caminos más cortos en arreglos en línea, archivado desde el original el 3 de diciembre de 2008 , consultado el 15 de diciembre de 2008
• Fortuna, S.; Milenkovic, V. (1991), "Estabilidad numérica de algoritmos para disposiciones de líneas", Proc. Séptimo Simposio ACM sobre geometría computacional (SoCG '91) , págs. 334–341, CiteSeerX  10.1.1.56.2404 , doi :10.1145/109648.109685, ISBN 978-0897914260, S2CID  2861855
• de Fraysseix, H.; Ossona de Méndez, P. (2003), "Estiramiento de los sistemas de contacto del 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 una gran cantidad de triángulos" (PDF) , Actas de la Sociedad Matemática Estadounidense , 92 (4): 561–566, doi :10.2307/2045427, JSTOR  2045427, archivado ( PDF) del original el 3 de marzo de 2016 , consultado el 15 de diciembre de 2008
• Goodman, Jacob E .; Pollack, Richard (1993), "Secuencias permitidas y tipos de orden en geometría discreta y computacional", en Pach, János (ed.), Nuevas tendencias en geometría , algoritmos y combinatoria discreta y computacional, 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, Refael; Zamfirescu, Tudor (1994), "Todo arreglo 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, S2CID  2624319
• Grünbaum, B. (1972), Arreglos y extensiones , Serie de conferencias regionales sobre matemáticas, vol. 10, Providence, RI: Sociedad Matemática Estadounidense
• Grünbaum, B. (1974), Notas sobre arreglos , Universidad de Washington, hdl :1773/15699; ver pág. 6 de "arreglos euclidianos" (p. 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 , SEÑOR  2485643
• Halperin, D.; Sharir, M. (2018), "Arrangements", en Goodman, Jacob E.; O'Rourke, José; 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, señor  3793131
• Kelly, LM ; Moser, WOJ (1958), "Sobre el número de líneas ordinarias determinadas por n puntos", Canadian Journal of Mathematics , 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 , Serie Fundamentos de la Computación, 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, señor  1410263
• Matoušek, J. (1991), "Límites inferiores de la longitud de trayectorias monótonas en arreglos", Geometría computacional y discreta , 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 informática (FOCS '89) , págs. doi :10.1109/SFCS.1989.63525, ISBN 978-0-8186-1982-3, S2CID  18564700
• 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 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, señor  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, señor  1640615
• Purdy, GB (1979), "Triángulos en disposición 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 Sociedad Matemática Estadounidense , 79 : 77–81, doi : 10.1090/S0002-9939-1980-0560588-4
• Roudneff, J.-P. (1988), "Las disposiciones 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, 17º Simposio Internacional, GS 2009, Chicago, IL, EE. UU., septiembre de 2009, artículos 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) desde el 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: Victor Klee Festschrift , Serie DIMACS en matemáticas discretas e informática teórica, vol. 4, Providence, RI: Sociedad Matemática Estadounidense, 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 disposición 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), "Cruce de números y problemas difíciles de Erdős en geometría discreta" (PDF) , Combinatoria, probabilidad y computación , 6 (3): 353–358, doi :10.1017/S0963548397002976, S2CID  36602807, archivado (PDF) del original el 2017-08-08 , recuperado el 2019-09-23
• Tóth, G. (2001), "Conjuntos de puntos con muchos k -conjuntos", Geometría computacional y discreta , 26 (2): 187–194, doi : 10.1007/s004540010022

enlaces externos

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