En geometría, una disposición de líneas es la partición del plano formada por una colección de líneas . Los límites de la complejidad de los arreglos se han estudiado en geometría discreta , y los geómetras computacionales han encontrado algoritmos para la construcción eficiente de arreglos.
Definición
Para cualquier conjunto de rectas en el plano euclidiano , se puede definir una relación de equivalencia en los puntos del plano según la cual dos puntos y son equivalentes si, para cada línea de , ya sea y ambos están en o ambos pertenecen al mismo semiplano abierto limitado por. Cuándoes finito o localmente finito [1] las clases de equivalencia de esta relación son de tres tipos:
- los interiores de polígonos convexos limitados o ilimitados (las celdas o cámaras de la disposición), los componentes conectados del subconjunto del plano no contenidos en ninguna de las líneas de,
- segmentos de línea abiertos y rayos infinitos abiertos (los bordes o paneles de la disposición), los componentes conectados de los puntos de una sola línea que no pertenecen a ninguna otra línea de, y
- puntos únicos (los vértices de la disposición), las intersecciones de dos o más líneas de.
Estos tres tipos de objetos se unen para formar un complejo celular que cubre el plano. Se dice que dos disposiciones son isomórficas o combinatoriamente equivalentes si hay una correspondencia uno a uno que preserva la adyacencia entre los objetos en sus complejos celulares asociados. [2]
Complejidad de arreglos
El estudio de los arreglos fue iniciado por Jakob Steiner , quien probó los primeros límites sobre el número máximo de características de diferentes tipos que puede tener un arreglo. [3] Un acuerdo con líneas tiene como máximo vértices (un número triangular ), uno por par de líneas que se cruzan. Este máximo se logra para arreglos simples , aquellos en los que cada dos líneas tiene un par distinto de puntos de cruce. En cualquier arreglo habrárayos infinitos hacia abajo, uno por línea; estos rayos se separanceldas de la disposición que son ilimitadas en la dirección descendente. Todas las celdas restantes tienen un vértice inferior único, [4] y cada vértice es el último para una celda única, por lo que el número de celdas en una disposición es el número de vértices más, o como mucho ; vea la secuencia del catering perezoso . El número de bordes del arreglo es como máximo, como puede verse 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 bordes por el otro líneas; nuevamente, este límite del peor de los casos se logra para arreglos simples.
La zona de una línea en una disposición de línea es la colección de celdas que tienen bordes pertenecientes a . El teorema de la zona establece que el número total de bordes 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 , [5] y el número total de bordes de las celdas que pertenecen a ambos lados de es como máximo . [6] 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, dónde denota la función de Ackermann inversa , como puede mostrarse usando secuencias de Davenport-Schinzel . [6] Sumando las complejidades de todas las zonas, se encuentra que la suma de cuadrados de las complejidades de las celdas en un arreglo es. [7]
La - el nivel de una disposición es la cadena poligonal formada por los bordes que tienen exactamente otras lneas directamente debajo de ellos, y el -nivel es la parte del arreglo debajo del -nivel. Encontrar límites superior e inferior coincidentes para la complejidad de un-el nivel sigue siendo un gran problema abierto en geometría discreta; el mejor límite superior es, mientras que el mejor límite inferior es . [8] Por el contrario, la máxima complejidad de la-se sabe que el nivel es . [9] A-level es un caso especial de una ruta monótona en un arreglo; es decir, una secuencia de aristas que interseca cualquier línea vertical en un solo punto. Sin embargo, los caminos monótonos pueden ser mucho más complicados que-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 . [10]
Aunque una sola celda en un arreglo puede estar delimitada por todos líneas, no es posible en general para diferentes celdas para que todas estén delimitadas por líneas. Más bien, la complejidad total de células es como máximo , [11] casi el mismo límite que ocurre en el teorema de Szemerédi-Trotter sobre las incidencias de la línea de puntos en el plano. Una prueba simple de esto se deriva de la desigualdad de números cruzados : [12] si las celdas tienen un total de bordes, uno puede formar un gráfico con nodos (uno por celda) y bordes (uno 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 lo tanto, haycruces en este dibujo. Sin embargo, por la desigualdad de números cruzados, haycruces; para satisfacer ambos límites, debe ser . [13]
Arreglos proyectivos y dualidad proyectiva
A menudo es conveniente estudiar los arreglos de líneas no en el plano euclidiano sino en el plano proyectivo , debido al hecho de que en la geometría proyectiva cada par de líneas tiene un punto de cruce. En el plano proyectivo, es posible que ya no definamos arreglos usando lados de líneas (una línea en el plano proyectivo no separa el plano en dos lados distintos), pero aún podemos definir las celdas de un arreglo como los componentes conectados del los puntos que no pertenecen a ninguna línea, las aristas son los componentes conectados de conjuntos de puntos que pertenecen a una sola línea, y los vértices son puntos donde se cruzan dos o más líneas. Una disposición de línea 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 ese par de Las celdas euclidianas ilimitadas se reemplazan en el plano proyectivo por celdas individuales que son cruzadas por la línea proyectiva en el infinito.
Debido a la dualidad proyectiva , muchos enunciados sobre las propiedades combinatorias de puntos en el plano pueden entenderse más fácilmente en una forma dual equivalente sobre arreglos de líneas. Por ejemplo, el teorema de Sylvester-Gallai , que establece que cualquier conjunto de puntos no colineales en el plano tiene una línea ordinaria que contiene exactamente dos puntos, se transforma bajo dualidad proyectiva en el enunciado de que cualquier disposición de líneas con más de un vértice tiene una línea ordinaria punto , un vértice donde solo se cruzan dos líneas. La prueba más antigua conocida del teorema de Sylvester-Gallai, de Melchior (1940) , utiliza la característica de Euler para mostrar que tal vértice debe existir siempre.
Triángulos en arreglos
Se dice que una disposición de líneas en el plano proyectivo es simple si cada celda de la disposición está delimitada exactamente por tres bordes; Los arreglos simpliciales fueron estudiados por primera vez por Melchor. [14] Se conocen tres familias infinitas de arreglos de líneas simples:
- Un lápiz que consta de líneas a través de un solo punto, junto con una sola línea adicional que no pasa por el mismo punto,
- La familia de líneas formadas por los lados de un polígono regular junto con sus ejes de simetría , y
- 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 simples esporádicos que no encajan en ninguna familia infinita conocida. [15] Como escribe Grünbaum [16] , los arreglos simples "aparecen como ejemplos o contraejemplos en muchos contextos de geometría combinatoria y sus aplicaciones". Por ejemplo, Artés, Grünbaum y Llibre (1998) utilizan arreglos simples para construir contraejemplos a 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-La disposición de la línea tiene al menos puntos ordinarios) son ambos simples. [17]
El gráfico dual de una disposición de línea, en el que hay un nodo por celda y un borde que une cualquier par de celdas que comparten un borde de la disposición, es un cubo parcial , un gráfico en el que los nodos se pueden etiquetar por vectores de bits en tal una forma en que la distancia del gráfico es 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. [18] Se han utilizado gráficos duales de arreglos simples para construir familias infinitas de cubos parciales regulares de 3 , isomorfos a los gráficos de zonoedros simples . [19]
También es de interés estudiar el número extremo de celdas triangulares en arreglos que pueden no ser necesariamente simples. En cualquier arreglo, debe haber al menostriangulos; cada arreglo que tiene sololos triángulos deben ser simples. [20] Se sabe que el número máximo posible de triángulos en una disposición simple está delimitado en la parte superior por y menor delimitado por ; el límite inferior se logra mediante ciertos subconjuntos de las diagonales de una regular-gon. [21] Para arreglos no simples, el número máximo de triángulos es similar pero más estrechamente acotado. [22] El problema del triángulo de Kobon estrechamente relacionado pide el número máximo de triángulos finitos no superpuestos (no necesariamente caras) en una disposición en el plano euclidiano; para algunos pero no todos los valores de, los triángulos son posibles.
Revestimientos multirredes y Penrose
El gráfico dual de una disposición de línea 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. de Bruijn (1981) investigó casos especiales de esta construcción en los que el arreglo lineal consiste enconjuntos de líneas paralelas igualmente espaciadas. Para dos familias perpendiculares de líneas paralelas, esta construcción solo da el mosaico cuadrado familiar del plano, y para tres familias de líneas en ángulos de 120 grados entre sí (formando ellas mismas un mosaico trihexagonal ), esto produce el mosaico rhombille . 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 pentagrid ), produce una familia de mosaicos que incluyen la versión rómbica de los mosaicos de Penrose .
El mosaico cuadrado 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 la que dos de las familias están más espaciadas que las otras dos, y en la que la disposición es más simple que simple. Su dual es el mosaico cuadrado truncado . De manera similar, el mosaico triangular es una disposición de línea simplicial infinita con tres familias paralelas, que tiene como doble el mosaico hexagonal , y el mosaico hexagonal bisecado es una disposición de línea simplicial infinita con seis familias paralelas y dos espaciamientos de línea, dual al gran rombitrihexagonal. baldosas .
Algoritmos
Construir una disposición significa dar como entrada una lista de las líneas en la disposición, calcular una representación de los vértices, aristas y celdas de la disposición junto con las adyacencias entre estos objetos, por ejemplo, como una lista de aristas doblemente conectadas . Debido al teorema de la zona, los arreglos se pueden construir de manera eficiente 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 el tiempo proporcional a su zona, lo que resulta en un tiempo total de construcción de. [5] 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 una disposición mediante un algoritmo que no mantenga la disposición completa en la memoria a la vez. Esto se puede hacer nuevamente de manera eficiente, a tiempo y espacio , mediante una técnica algorítmica conocida como barrido topológico . [23] Calcular una disposición de línea con exactitud 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 en ella, las coordenadas de los vértices de la disposición pueden necesitar cuatro veces más precisión que estos puntos de entrada . Por lo tanto, los geómetras computacionales también han estudiado algoritmos para construir arreglos de manera eficiente con precisión numérica limitada. [24]
Además, los investigadores han estudiado algoritmos eficientes para construir porciones más pequeñas de un arreglo, como zonas, [25] -niveles, [26] o el conjunto de celdas que contienen un conjunto dado de puntos. [27] El problema de encontrar el vértice de la disposición con la medianaLa coordenada surge (en forma dual) en las estadísticas robustas como el problema de calcular el estimador de Theil-Sen de un conjunto de puntos. [28]
Marc van Kreveld sugirió el problema algorítmico de calcular las rutas más cortas entre vértices en una disposición de línea, donde las rutas están restringidas para 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. [29] Se conoce un algoritmo de aproximación , [30] y el problema puede resolverse eficientemente para líneas que caen en un pequeño número de familias paralelas (como es típico de las cuadrículas de calles urbanas), [31] pero el problema general permanece abierto.
Arreglos de líneas no euclidianas
Una disposición de pseudolina es una familia de curvas que comparten propiedades topológicas similares con una disposición de línea. [32] Estos pueden definirse de manera más simple en el plano proyectivo como simples curvas cerradas, dos de las cuales se encuentran en un solo punto de cruce. [33] Se dice que una disposición de pseudolina es estirable si es combinatoriamente equivalente a una disposición de línea; es completo para la teoría existencial de los reales distinguir los arreglos extensibles de los no extensibles. [34] Cada disposición de un número finito de pseudolinas puede extenderse 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.
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. 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, en arreglos de líneas hiperbólicas, las líneas pueden evitar cruzarse entre sí sin ser paralelas; el gráfico de intersección de las líneas en una disposición hiperbólica es un gráfico circular . El concepto correspondiente a los arreglos de líneas hiperbólicas para las pseudolinas es un arreglo de pseudolinas débil , [35] una familia de curvas que tienen las mismas propiedades topológicas que las líneas [36], de modo que dos curvas cualesquiera de la familia se encuentran en un solo punto de cruce o no tienen intersección.
Ver 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 que pertenecen al mismo número de líneas
- Disposición (partición espacial) , una partición del plano dada por curvas superpuestas o de un espacio dimensional superior por superficies superpuestas, sin requerir que las curvas o superficies sean planas
- K-set (geometría) , relacionado por dualidad proyectiva con-Niveles en arreglos de línea.
- Mathematical Bridge , un puente en Cambridge, Inglaterra, cuyas vigas forman una disposición de líneas tangentes a su arco.
Notas
- ↑ Para que una disposición sea localmente finita, cada subconjunto acotado del plano puede estar cruzado sólo por un número finito de líneas.
- ^ Grünbaum (1972) , página 4.
- ↑ Steiner (1826) ; Agarwal y Sharir (2000) .
- ^ Para las celdas en las que hay un borde inferior horizontal, elija el vértice más inferior para que sea el punto final derecho del borde inferior.
- ↑ a b Chazelle, Guibas y Lee (1985) , Edelsbrunner (1987) , Edelsbrunner, O'Rourke y Seidel (1986) .
- ^ a b Berna y col. (1991) .
- ^ Aronov, Matoušek y Sharir (1994) .
- ^ Dey (1998) ; Tóth (2001) . El problema de delimitar la complejidad de losniveles k 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 col. (1990) .
- ^ Ajtai y col. (1982) ; Leighton (1983) .
- ^ Székely (1997) .
- ↑ Melchior (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) .
- ^ Eppstein (2006) .
- ^ Grünbaum (1972) ; Levi (1926) ; Roudneff (1988) .
- ^ Füredi y Palásti (1984) ; Grünbaum (1972) .
- ^ Purdy (1979) ; Purdy (1980) ; Strommer (1977) .
- ^ 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) .
- ^ Bose 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 pseudolinas, consulte Eppstein, Falmagne & Ovchinnikov (2007) .
- ^ Shor (1991) ; Schaefer (2010) .
- ↑ de Fraysseix y Ossona de Mendez (2003) .
- ^ Aquíes apropiadauna definición alternativa de Shor (1991) , que una pseudolina es la imagen de una línea debajo de un homeomorfismo del plano.
Referencias
- 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), "Computación de muchas caras en arreglos 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.), Manual de geometría computacional , Elsevier, págs. 49-119.
- Agarwal, PK ; Sharir, M. (2002), "Arreglos de pseudolínea : 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", Matemáticas discretas , 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, 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, 60 , Holanda del Norte, págs. 9-12, MR 0806962.
- Alon, 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 arreglos 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.
- Balogh, J .; Regev, O .; Smyth, C .; Steiger, W .; Szegedy, M. (2004), "Rutas largas y monótonas en arreglos de líneas", Geometría discreta y computacional , 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 de DIMACS, DIMACS Ser. Matemáticas discretas. y Ciencias de la Computación Teóricas (6 ed.), Amer. Matemáticas. Soc., Págs. 45–66, MR 1143288.
- Bose, P .; Evans, W .; Kirkpatrick, DG ; McAllister, M .; Snoeyink, J. (1996), "Aproximación de caminos más cortos en arreglos de líneas", Proc. Octava Conf. Canadiense Geometría computacional , págs. 143-148.
- de Bruijn, NG (1981), "Teoría algebraica de las teselaciones no periódicas del plano de Penrose" (PDF) , Indagationes Mathematicae , 43 : 38–66.
- Canham, R. (1969), "Un teorema sobre arreglos de líneas en el plano", Israel J. Math. , 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 k- cascos y problemas relacionados", SIAM Journal on Computing , 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.
- Edelsbrunner, H. (1987), Algoritmos en geometría combinatoria , EATCS Monografías en informática teórica, Springer-Verlag, ISBN 978-3-540-13722-1.
- Edelsbrunner, H .; Guibas, LJ (1989), "Topológicamente barriendo 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 de 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 arreglos bidimensionales con aplicaciones", SIAM Journal on Computing , 15 (1): 271-284, doi : 10.1137 / 0215019.
- Eppstein, D. (2006), "Cubos parciales cúbicos de arreglos simples " , Electronic Journal of Combinatorics , 13 (1, R79): 1-14, arXiv : math.CO/0510263 , doi : 10.37236 / 1105 , MR 2255421 , S2CID 8608953.
- Eppstein, D .; Falmagne, J.-Cl. ; Ovchinnikov, S. (2007), Teoría de los medios , Springer-Verlag.
- Eppstein, D .; Hart, D. (1999), "Rutas más cortas en un arreglo con k orientaciones de línea" , Actas del décimo 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, Colorado, 1971) , Amsterdam: North-Holland, págs. 139-149, MR 0363986.
- Erickson, J. (1997), Rutas más cortas en arreglos de línea , 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. Séptimo Simposio de 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 de arco de Jordan", Actas del XI Simposio Internacional sobre Dibujo de Gráficos (GD 2003) , Lecture Notes in Computer Science (2912 ed.), Springer-Verlag, pp. 71–85.
- Füredi, Z .; Palásti, I. (1984), "Arreglos 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
- Greene, D .; Yao, FF (1986), "Geometría computacional de resolución finita", Actas del 27º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (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 Spreads , Serie de Conferencias Regionales en Matemáticas, 10 , Providence, RI: American Mathematical Society.
- 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.
- 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.
- 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. Math.-Phys. Kl. Sächs. Akad. 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.
- Matoušek, J. (1991), " Límites inferiores en la longitud de trayectorias monótonas en 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 las intersecciones de líneas y segmentos utilizando aritmética redondeada", Actas del 30º Simposio de 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, S2CID 18564700.
- 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.
- Purdy, GB (1979), "Triángulos en arreglos de líneas", Matemáticas discretas , 25 (2): 157-163, doi : 10.1016 / 0012-365X (79) 90018-9.
- Purdy, GB (1980), "Triángulos en arreglos de líneas, II", Proceedings of the 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) , Dibujo de gráficos, 17th International Symposium, GS 2009, Chicago, IL, EE. UU., Septiembre de 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Springer-Verlag, págs. 334–344, doi : 10.1007 / 978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
- Shor, PW (1991), "Stretchability of pseudolines is NP-hard", en Gritzmann, P .; Sturmfels, B. (eds.), Geometría aplicada y matemáticas discretas: The Victor Klee Festschrift , Serie DIMACS en matemáticas discretas y ciencias de la computación teóricas, 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 difíciles de Erd en geometría discreta" (PDF) , Combinatoria, Probabilidad y Computación , 6 (3): 353–358, doi : 10.1017 / S0963548397002976.
- Tóth, G. (2001), "Conjuntos de puntos con muchos conjuntos k ", Geometría discreta y computacional , 26 (2): 187-194, doi : 10.1007 / s004540010022.
enlaces externos
- Base de datos de arreglos de líneas combinatoriamente diferentes