Configuración de línea recta

Una configuración de líneas (o una partición de un plano por líneas ) [1]  es una partición de un plano formada por un conjunto de líneas . Las configuraciones de línea se estudian en geometría combinatoria , y en geometría computacional , los algoritmos se construyen para construir configuraciones de manera eficiente.

Definición

Para cualquier conjunto A de rectas sobre el plano euclidiano , se puede definir una relación de equivalencia sobre puntos del plano, según la cual dos puntos p y q son equivalentes si, para cualquier recta l desde A , tanto p como q se encuentran en el línea l , o se encuentran en el mismo semiplano abierto delimitado por la línea recta l . Si A es finito o localmente finito [2] , las clases de equivalencia de estas relaciones pertenecen a tres grupos:

  1. interiores de polígonos convexos acotados o no acotados ( celdas de descomposición ), componentes conectados de un subconjunto de puntos en el plano no contenidos en ninguna de las líneas de A ,
  2. segmentos abiertos y rayos infinitos abiertos ( aristas de descomposición ), componentes conexas de puntos de una sola línea que no pertenecen a ninguna otra línea de A ,
  3. puntos separados ( vértices de la partición), la intersección de dos o más líneas de A .

Estos tres tipos de objetos, conectados entre sí, forman un mosaico que cubre el plano. Se dice que los arreglos de dos líneas son isomorfos o combinatoriamente equivalentes si existe una correspondencia uno a uno que preserva la adyacencia entre los objetos en las particiones de celdas [3]

Complejidad de conjuntos

El estudio de las configuraciones de comienzos directos de Jacob Steiner , quien demostró el primer límite sobre el número máximo de elementos de diferentes tipos que puede contener una configuración [4] [5] . Una configuración de n líneas tiene como máximo n ( n  − 1)/2 vértices, uno por par de vértices que se cruzan. Este máximo se alcanza en configuraciones simples . Una configuración se llama simple si

1. no hay tres líneas que se crucen en un punto 2. no hay dos líneas paralelas.

En cualquier configuración habrá n infinitos rayos hacia abajo, uno por línea. Estos rayos separan n  + 1 celdas de la partición, que son ilimitadas desde abajo. Todas las celdas restantes tienen un solo vértice más bajo, [6] y cada uno de esos vértices es el más bajo para una sola celda, por lo que el número de celdas de partición es igual al número de vértices más n  + 1 o no excede n ( n  + 1)/2 + 1, ver abajo números poligonales centrales . El número de aristas de partición no excede de n 2 , lo que se puede ver usando la característica de Euler , sustituyendo el número de vértices y celdas, o usando la observación de que cada línea se divide en como máximo n aristas por otras n  − 1 líneas. Nuevamente, el peor caso donde se alcanza el límite son las configuraciones de línea simple.

La zona de una línea l en un conjunto de líneas es un conjunto de celdas que tienen bordes que se encuentran en l . 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 celda (de la zona de la línea) ubicados en un lado de la línea l no excede 5 n  − 1 [7] [8] [9] , y el número total de bordes de celda que se encuentran en ambos lados de l no excede [10] . De manera más general, la complejidad total de las celdas de partición que se cruzan con una curva convexa es O( n  α( n )), donde α denota la función inversa de Ackermann , que se puede mostrar a partir de las secuencias de Davenport-Schinzel [10] . Resumiendo la complejidad de todas las zonas, se puede encontrar que la suma de la complejidad al cuadrado de las celdas en la partición es O( n 2 ) [11] .

El nivel k de la configuración de líneas es unapolilíneaformada por aristas que tienen exactamentekotras líneas debajo (es decir, el rayo dibujado desde la arista corta exactamenteklíneas), yel nivel ≤k es todas las configuraciones de línea de partes bajo elk. Encontrar límites de complejidad superior e inferior parak-niveles sigue siendo un gran problema abierto en geometría discreta. El mejor límite superior es O(nk1/3), mientras que el mejor límite inferior es Ω(nexp(c(logk)1/2)) [12] [13] [14] . Se sabe que la complejidad máxima de un nivel ≤kes Θ(nk) [15] . El nivel kes un caso especial de un camino monótono en una partición plana, es decir, una secuencia de aristas que se cruzan con cualquier línea vertical en un solo punto. Sin embargo, los caminos monótonos pueden ser más complicados quek: hay conjuntos de líneas y caminos monótonos en estos conjuntos, donde el número de puntos en los que el camino cambia de dirección es Ω(n2 − o(1)) [16] [17] .

Aunque una sola celda en una partición puede estar delimitada por todas las n líneas, en general no es posible que m celdas distintas estén delimitadas por n líneas. Por el contrario, la complejidad total de m celdas es casi igual a Θ( m 2/3 n 2/3  +  n ) [18] [19] y casi la misma frontera aparece en el teorema de Szemerédy-Trotter sobre la incidencia de puntos y rectas en el plano. Una prueba simple de este hecho se deriva de la desigualdad del número de intersección  : si m celdas tienen x  +  n aristas en total, puede crear un gráfico con m vértices (uno por celda) y x aristas (una por par de celdas consecutivas en el mismo línea) [20] [21] . Los bordes de este gráfico se pueden dibujar como curvas que no se cortan dentro de las celdas correspondientes a los vértices finales de los bordes y luego seguir las líneas rectas del conjunto. Por lo tanto, hay O( n 2 ) intersecciones en esta figura. Sin embargo, por la desigualdad del número de intersección, hay intersecciones Ω( x 3 / m 2 ). Para que se cumplan ambas desigualdades, x debe ser O( m 2/3 n 2/3 ) [22] .

Configuraciones proyectivas y dualidad proyectiva

A menudo es conveniente estudiar la configuración de las líneas no en el espacio euclidiano, sino en el plano proyectivo , ya que en geometría proyectiva cualquier par de líneas tiene un punto de intersección. En un plano proyectivo, no podemos definir una partición usando los lados de las líneas (una línea en un plano proyectivo no divide el plano en dos lados distintos), pero aún podemos definir celdas de partición como componentes conectados de puntos que no se encuentran en cualquier linea Los bordes serán componentes conectados que consisten en conjuntos de puntos pertenecientes a una sola línea, y los vértices serán puntos donde se cruzan dos o más líneas. El conjunto de líneas en el plano proyectivo difiere de su contraparte euclidiana, ya que los dos rayos euclidianos en ambos lados de la línea se reemplazan por un solo borde en el plano proyectivo, y los pares de celdas euclidianas ilimitadas se reemplazan en el plano proyectivo en solo células.

En vista de la dualidad proyectiva , muchas afirmaciones sobre las propiedades combinatorias de los puntos en el plano pueden entenderse de forma más sencilla en la forma dual equivalente sobre las configuraciones de las líneas. Por ejemplo, el teorema de Sylvester , que establece que cualquier conjunto no colineal de puntos en el plano tiene una línea simple , que contiene exactamente dos puntos, se convierte, por dualidad proyectiva, en el enunciado de que cualquier configuración de líneas que tiene más de un vértice tiene una línea simple . punto , el vértice en el que todas las dos líneas rectas. La demostración más antigua conocida del teorema de Sylvester por Melchior ( Melchior (1940 )) utiliza la característica de Euler .

Triángulos en conjuntos de líneas

Se dice que una configuración de líneas en el plano proyectivo es simplicial si cualquier celda de la partición está delimitada por exactamente tres bordes. Melchor [23] [24] estudió por primera vez las configuraciones simpliciales . Se conocen tres familias infinitas de conjuntos simpliciales de líneas:

  1. Una gavilla cercana consta de n  − 1 líneas que pasan por un punto y una línea que no pasa por este punto,
  2. La familia de rectas formada por los lados de un polígono regular junto con los ejes de simetría.
  3. Lados y ejes de simetría de un polígono regular par, junto con una recta en el infinito.

Además, hay muchos otros ejemplos de configuraciones simples simples que no encajan en ninguna familia infinita conocida [25] [24] . Como escribe Grünbaum [24] , los conjuntos de líneas simpliciales "aparecen como ejemplos o contraejemplos en muchos contextos de geometría combinatoria y sus aplicaciones". Por ejemplo, Artier, Grünbaum y Llibre [26] utilizaron conjuntos de líneas simpliciales para construir contraejemplos a la conjetura sobre la relación entre las potencias de un conjunto de ecuaciones diferenciales y el número de líneas invariantes que puede tener una ecuación. Dos conocidos contraejemplos de la conjetura de Dirac-Motzkin (que establece que cualquier configuración de n líneas tiene al menos n /2 puntos simples) son ambos simplicios [27] [28] [29] [30] .

El gráfico dual de una configuración lineal en la que hay un vértice por celda y una arista que conecta los vértices correspondientes a las celdas con una arista común en la configuración es un cubo parcial , un gráfico en el que los vértices se pueden etiquetar con vectores de bits tales que la distancia en el gráfico es igual a la distancia de Hamming entre marcas. En el caso de configuraciones de línea, cada coordenada toma el valor 0 para las aristas de un lado de la línea y 1 para las aristas del otro lado [31] . Los gráficos duales de configuraciones simpliciales se han utilizado para construir infinitas familias de cubos parciales de 3 regulares isomórficos a los gráficos de un zonoedro simple [32] .

También es interesante estudiar los números extremos de celdas triangulares en una configuración que no es necesariamente simplista. Cualquier configuración debe tener al menos n triángulos. Cualquier configuración con solo n triángulos debe ser simple [25] [33] [34] . Se sabe que el número máximo posible de triángulos en una configuración simple está acotado superiormente por el número n ( n  − 1)/3, y el límite mínimo es n ( n  − 3)/3. El límite inferior se alcanza en algunos subconjuntos de las diagonales de un 2 n -gon regular [35] [25] . Para configuraciones no simples, el número máximo de triángulos es similar pero más limitado [36] [37] [38] . El problema del triángulo de Cobon, estrechamente relacionado , pide el número máximo de triángulos finitos que no se superponen (no necesariamente caras) en una configuración en el plano euclidiano. Para algunos valores de n , pero no para todos, puede haber n ( n  − 2)/3 triángulos.

Teselaciones Multigrid y Penrose

El gráfico dual de una configuración simple de líneas se puede representar geométricamente como un conjunto de rombos , uno por vértice de la configuración, con lados perpendiculares a las líneas que se cortan en el vértice. Estos rombos se pueden combinar para formar un mosaico de un polígono convexo en el caso de una configuración con un número finito de líneas, o el plano completo en el caso de configuraciones localmente finitas con un número infinito de líneas. De Bruijn [39] estudió casos especiales de esta construcción, en los que la configuración de líneas consta de k conjuntos de líneas paralelas con la misma distancia entre sí. Para dos familias perpendiculares de líneas paralelas, esta construcción simplemente da el parquet cuadrado familiar en el plano, y para tres familias de líneas a 120 grados entre sí (formando así un mosaico trihexagonal ), la construcción da un mosaico rómbico . Sin embargo, para un mayor número de familias de líneas, esta construcción da teselaciones aperiódicas . En particular, para cinco familias de líneas en ángulos iguales entre sí (o, como de Bruijn llama a esta configuración, una pentarrejilla ), esto da una familia de mosaicos que incluye una versión rómbica de los mosaicos de Penrose .

Un mosaico cuadrado dividido  es una configuración infinita de líneas que forma una teselación periódica que se asemeja a una cuadrícula múltiple con cuatro familias paralelas, pero en la que dos familias tienen una mayor distancia entre líneas que las otras dos, y en el que el conjunto de líneas es simplicial más que sencillo. El mosaico dual es el mosaico cuadrado truncado . De manera similar, un mosaico triangular es una configuración simplicial infinita de líneas con tres familias de líneas paralelas, cuyo mosaico dual es un mosaico hexagonal , y un mosaico hexagonal dividido es una configuración simplicial infinita de líneas con seis familias de líneas paralelas y dos distancias entre líneas en las familias, que es dual al gran mosaico rómbico-trihexagonal .

Algoritmos

Construir una configuración significa calcular la representación de los vértices, las aristas y las celdas de una configuración de línea (junto con sus relaciones) cuando se da una lista de líneas en un conjunto, como una lista de aristas doblemente enlazadas . De acuerdo con el teorema de la zona, los conjuntos se pueden construir de manera eficiente con un algoritmo incremental que agrega una línea por paso al conjunto de líneas agregado en los pasos anteriores; cada nueva línea se puede agregar en un tiempo proporcional a su zona, lo que da como resultado el tiempo O( n 2 ) [7] . Sin embargo, los requisitos de memoria de este algoritmo son altos, por lo que puede ser más conveniente enumerar todas las propiedades de configuración en un algoritmo que no almacene toda la configuración en la memoria. Esto se puede hacer de manera eficiente en el tiempo O( n 2 ) y en el espacio O( n ) utilizando una técnica algorítmica conocida como balayage topológico [40] . El cálculo preciso de la configuración de la línea requiere una precisión computacional varias veces mayor que los datos de entrada (coordenadas); si la línea está dada por dos puntos, las coordenadas de la configuración del vértice pueden requerir cuatro veces la precisión de los puntos de datos de entrada. Por lo tanto, los algoritmos para construir configuraciones de manera eficiente con precisión numérica limitada también se estudian en geometría computacional [41] [42] [43] .

Los investigadores también estudiaron algoritmos eficientes para construir partes más pequeñas de una configuración, como zonas [44] , niveles k [45] [46] [47] [48] o un conjunto de celdas que contienen un conjunto dado de puntos [49] [50] [51] . El problema de encontrar una configuración de vértices con coordenadas x medianas surge (en una forma dual) en estadística robusta como el problema de calcular la estimación de Theil-Sen de un conjunto de puntos [52] .

Mark van Creveld propuso un problema algorítmico para calcular el camino más corto entre vértices en una configuración de líneas donde los caminos están limitados por los bordes de la configuración. El problema se plantea de la siguiente manera: ¿existen algoritmos que funcionen en menos de un tiempo cuadrático que emplearía el algoritmo para encontrar el camino más corto en un gráfico de configuración completo [53] ? Se conoce un algoritmo de aproximación [54] , y el problema se puede resolver de manera efectiva para líneas que se dividen en un pequeño número de familias de líneas paralelas (lo que es típico de las calles de la ciudad) [55] , pero el problema en general permanece abierto.

Variaciones y generalizaciones

Configuración de pseudolínea

Una configuración de pseudolíneas  es una configuración de curvas que tienen propiedades topológicas similares a una configuración de líneas [25] [56] . Pueden definirse más simplemente en el plano proyectivo como simples curvas cerradas, de las cuales dos se cruzan transversalmente en un solo punto. Se dice que una configuración de pseudolíneas es extensible si es combinatoriamente equivalente a una configuración de líneas. El problema de distinguir los conjuntos rectificables de los no rectificables [57] [58] es NP-completo . Cualquier configuración de un número finito de pseudolíneas se puede extender para que las pseudolíneas se conviertan en líneas en una geometría de incidencia no euclidiana , en la que dos puntos cualesquiera del plano topológico están conectados por una sola línea (como en el plano euclidiano), pero en que los otros axiomas de la geometría euclidiana pueden no cumplirse.


Conjunto inextensible de nueve pseudolíneas. (Todas las colecciones con menos de nueve pseudolíneas son rectificables). Por el teorema de Pappus , esta configuración no se puede realizar en el plano proyectivo sobre ningún campo.
La configuración hiperbólica de líneas es combinatoriamente equivalente al diagrama de cuerdas utilizado por Ageev [59] para probar que un gráfico circular sin triángulos a veces puede requerir cinco colores .

Plano de Lobachevsky

Otro tipo de geometría no euclidiana es el plano de Lobachevsky , y también se han estudiado configuraciones de líneas hiperbólicas en esta geometría. Cualquier conjunto finito de líneas en el plano euclidiano tiene una configuración combinatoriamente equivalente en el plano hiperbólico (por ejemplo, encerrando los vértices del conjunto en un gran círculo e interpretando el interior del ciclo como un modelo de Klein del plano hiperbólico). Sin embargo, en un conjunto hiperbólico de líneas es posible evitar la intersección de líneas sin el requisito de que las líneas sean paralelas. El gráfico de intersección de líneas en la configuración hiperbólica es un gráfico circular . La noción correspondiente de una configuración hiperbólica de líneas para pseudolíneas es una configuración débil de pseudolíneas [60] , una familia de curvas que tiene las mismas propiedades topológicas que las líneas [61] tal que dos curvas cualesquiera de la familia se cruzan en un punto o no no se cruzan en absoluto.

Véase también

Notas

  1. ↑ En la literatura inglesa , arreglo , que a menudo se traduce como configuración , sin embargo, hay otro término configuración , que también se traduce naturalmente como la palabra configuración . A veces se usa el término conjunto de líneas , a veces - partición (por líneas o hiperplanos).
  2. ↑ En conjuntos localmente finitos, cualquier subconjunto acotado del plano solo puede ser intersecado por un número finito de líneas.
  3. ↑ Grünbaum, 1972 , pág. cuatro
  4. ↑ Steiner, 1826 .
  5. ↑ Agarwal, Sharir, 2000 .
  6. ↑ Para celdas que tienen un borde inferior horizontal, seleccione el vértice a la derecha.
  7. ↑ 12 Chazelle y otros, 1985 .
  8. ↑ Edelsbrunner, 1987 .
  9. ↑ Edelsbrunner, O'Rourke, Seidel, 1986 .
  10. ↑ 1 2 Berna, Eppstein, Plassman, Yao, 1991 .
  11. ↑ Aronov, Matousek, Sharir, 1994 .
  12. ↑ Dey, 1998 .
  13. ↑ Toth, 2001 .
  14. ↑ El problema de limitar la complejidad de los k -niveles fue estudiado por primera vez por Lovász (1971 ) y el grupo de Erdős, Simons, Straus ( Erdős et al (1973 )).
  15. ↑ Alon, Győri, 1986 .
  16. ↑ Balogh y otros, 2004 .
  17. ↑ Matousek, 1991 .
  18. ↑ Canham, 1969 .
  19. ↑ Clarkson y otros, 1990 .
  20. ↑ Ajtai, Chvátal, Newborn, Szemerédi, 1982 .
  21. ↑ Leighton, 1983 .
  22. ↑ Székely, 1997 .
  23. ↑ Melchor, 1940 .
  24. ↑ 1 2 3 Grünbaum, 2005 .
  25. ↑ 1 2 3 4 Grünbaum, 1972 .
  26. ↑ Artés, Grünbaum, Llibre, 1998 .
  27. ↑ Crowe, McKee, 1968 .
  28. ↑ Dirac, 1951 .
  29. ↑ Kelly, Moser, 1958 .
  30. ↑ Grünbaum, 1972 , pág. Dieciocho.
  31. ↑ Eppstein, Falmagne, Ovchinnikov, 2007 .
  32. ↑ Epstein, 2006 .
  33. ↑ Lévi, 1926 .
  34. ↑ Roudneff, 1988 .
  35. ↑ Füredi, Palásti, 1984 .
  36. ↑ Purdy, 1979 .
  37. ↑ Purdy, 1980 .
  38. ↑ Strommer, 1977 .
  39. ↑ de Bruijn, 1981 .
  40. ↑ Edelsbrunner, Guibás, 1989 .
  41. ↑ Fortuna, Milenkovic, 1991 .
  42. ↑ Greene, Yao, 1986 .
  43. ↑ Milenkovic, 1989 .
  44. ↑ Aharoni y otros, 1999 .
  45. ↑ Agarwal, de Berg, Matousek, Schwarzkopf, 1998 .
  46. ↑ Chan, 1999 .
  47. ↑ Cole, Sharir, Yap, 1987 .
  48. ↑ Edelsbrunner, Welzl, 1986 .
  49. ↑ Agarwal, 1990 .
  50. ↑ Agarwal, Matousek, Sharir, 1998 .
  51. ↑ Edelsbrunner, Guibas, Sharir, 1990 .
  52. ↑ Cole, Salowe, Steiger, Szemerédi, 1989 .
  53. ↑ Erikson, 1997 .
  54. ↑ Bose y otros, 1996 .
  55. ↑ Eppstein, Hart, 1999 .
  56. ↑ Agarwal, Sharir, 2002 .
  57. ↑ Shor, 1991 .
  58. ↑ Schaefer, 2010 .
  59. ↑ Ageev, 1996 .
  60. ↑ de Fraysseix, Ossona de Méndez, 2003 .
  61. ↑ Definición alternativa de Shor (1991 ): una pseudolínea es la imagen de una línea de un homeomorfismo plano .

Literatura

Enlaces