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:
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.
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.
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]
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]
El número de aristas de la disposición es como máximo , 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]
Las características más complejas reciben los nombres de "zonas", "niveles" y "muchas caras":
La zona de una línea en una disposición de líneas es el conjunto de celdas que tienen aristas que pertenecen a . 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 es como máximo , [7] y el número total de bordes de las celdas que pertenecen a ambos lados es como máximo . [8] 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 , 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]
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]
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]
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
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:
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,
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]
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]
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]
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] 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 y el espacio , 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]
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
^ Grünbaum (1972), pág. 4.
^ Eppstein, Falmagne y Ovchinnikov (2007), págs. 177-178.
^ ab Chazelle, Guibas y Lee (1985), Edelsbrunner (1987), Edelsbrunner, O'Rourke y Seidel (1986).
^ Berna y col. (1991); un manuscrito inédito de Rom Pinchasi de 2011 afirma tener una encuadernación ligeramente más fuerte .
^ Berna y col. (1991).
^ Aronov, Matoušek y Sharir (1994).
^ 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).
^ Alon y Győri (1986).
^ Balogh y col. (2004); véase también Matoušek (1991).
^ Canham (1969); Clarkson y cols. (1990).
^ Ajtai y otros. (mil novecientos ochenta y dos); Leighton (1983).
^ Székely (1997).
^ 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"
^ Polster (1998), pág. 223.
^ Goodman y Pollack (1993), pág. 110.
^ Esta es la prueba más antigua citada por Borwein y Moser (1990), pero escriben que probablemente otros dieron la misma prueba "mucho antes".
^ Melchor (1940); Grünbaum (2009).
^ Grünbaum (1972); Grünbaum (2009).
^ Grünbaum (2009).
^ Crowe y McKee (1968); Dirac (1951); Kelly y Moser (1958); Grünbaum (1972), página 18.
^ Eppstein, Falmagne y Ovchinnikov (2007), pág. 180.
^ Eppstein (2006).
^ Grünbaum (1972); Leví (1926); Roudneff (1988).
^ Grünbaum (1972).
^ Füredi y Palasti (1984); Grünbaum (1972).
^ Purdy (1979); Purdy (1980); Strommer (1977).
^ Moreno y Prieto-Martínez (2021).
^ Klee (1938).
^ de Bruijn (1981).
^ Abramenko y Brown (2008).
^ Edelsbrunner y Guibas (1989).
^ Fortuna y Milenkovic (1991); Greene y Yao (1986); Milenkovic (1989).
^ Aharoni y col. (1999).
^ Agarwal y col. (1998); Chan (1999); Cole, Sharir y Yap (1987); Edelsbrunner y Welzl (1986).
^ Agarwal (1990); Agarwal, Matoušek y Sharir (1998); Edelsbrunner, Guibas y Sharir (1990).
^ Cole y col. (1989).
^ Erickson (1997).
^ Bosé y col. (1996).
^ Eppstein y Hart (1999).
^ Grünbaum (1972); Agarwal y Sharir (2002).
^ Esta definición es de Grünbaum (1972). Para una comparación de definiciones alternativas de pseudolíneas, consulte Eppstein, Falmagne y Ovchinnikov (2007).
^ Corto (1991); Schäfer (2010).
^ Goodman y col. (1994).
^ Vestido, Koolen & Moulton (2002).
^ Martín (1996), págs.41, 338.
^ ab de Fraysseix y Ossona de Méndez (2003).
^ 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 ; 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.
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
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
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
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
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
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
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
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
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
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
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