stringtranslate.com

Disposición de líneas

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

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

Definición

Intuitivamente, cortar una hoja de papel infinita a lo largo de un número finito de líneas la dividiría en polígonos. Los bordes de estos polígonos serían segmentos de línea unidimensionales o rayos, con vértices producidos dondequiera que se crucen dos líneas cortadas. Esto se puede formalizar matemáticamente clasificando los puntos del plano según en qué lado de cada línea se encuentren. Cada línea produce tres posibilidades por punto: el punto puede estar en uno de los dos semiplanos abiertos a cada lado de la línea, o puede estar en la línea. Dos puntos pueden considerarse equivalentes si tienen la misma clasificación con respecto a todas las líneas. Esta es una relación de equivalencia , cuyas clases de equivalencia son subconjuntos de puntos equivalentes. Estos subconjuntos subdividen el plano en formas de los siguientes tres tipos: [1]

  1. Las celdas o cámaras del arreglo son regiones bidimensionales que no forman parte de ninguna línea. Forman el interior de polígonos convexos acotados o regiones convexas no acotadas. Estos son los componentes conectados de los puntos que quedarían después de eliminar todos los puntos de las líneas. [1]
  2. Los bordes o paneles de la disposición son regiones unidimensionales pertenecientes a una sola línea. Son los segmentos de línea abiertos y los rayos infinitos abiertos en los que cada línea está dividida 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, éstas son los componentes conexos de sus puntos no cortados. [1]
  3. Los vértices de la disposición son puntos aislados que pertenecen a dos o más líneas, donde dichas líneas se cruzan entre sí. [1]

El límite de una celda es el sistema de aristas que la tocan, y el límite de una arista es el conjunto de vértices que la tocan (un vértice para un rayo y dos para un segmento de línea). El sistema de objetos de los tres tipos, vinculados por este operador de límite, forma un complejo de celdas que cubre el plano. Se dice que dos disposiciones son isomorfas o combinatoriamente equivalentes si existe una correspondencia biunívoca que preserva el límite entre los objetos en sus complejos de celdas asociados. [1]

La misma clasificación de puntos y las mismas formas de clases de equivalencia se pueden utilizar para 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 las celdas no acotadas pueden tener un número infinito de lados. [3]

Complejidad de los acuerdos

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

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

Disposiciones proyectivas y dualidad proyectiva

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

Debido a la dualidad proyectiva , muchas afirmaciones sobre las propiedades combinatorias de los puntos en el plano pueden entenderse más fácilmente en una forma dual equivalente sobre las disposiciones de líneas. Por ejemplo, el teorema de Sylvester-Gallai , que establece que cualquier conjunto no colineal de puntos en el plano tiene una línea ordinaria que contiene exactamente dos puntos, se transforma bajo la dualidad proyectiva en la afirmación de que cualquier disposición proyectiva de un número finito de líneas con más de un vértice tiene un punto ordinario , un vértice donde solo se cruzan dos líneas. La primera prueba conocida del teorema de Sylvester-Gallai, de Melchior (1940), utiliza la característica de Euler para mostrar que dicho vértice siempre debe existir. [20]

Triángulos en arreglos

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

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

  1. Un lápiz casi completo que consta de líneas que pasan por un único punto, junto con una única línea adicional que no pasa por el mismo punto,
  2. La familia de líneas formadas por los lados de un polígono regular junto con sus ejes de simetría , y
  3. Los lados y ejes de simetría de un polígono regular par, junto con la línea en el infinito.

Además, hay muchos otros ejemplos de arreglos simpliciales esporádicos que no encajan en ninguna familia infinita conocida. [22] Como escribe Branko Grünbaum , los arreglos simpliciales "aparecen como ejemplos o contraejemplos en muchos contextos de geometría combinatoria y sus aplicaciones". [23] Por ejemplo, Artés, Grünbaum y Llibre (1998) utilizan arreglos simpliciales para construir contraejemplos a una conjetura sobre la relación entre el grado de un conjunto de ecuaciones diferenciales y el número de líneas invariantes que pueden tener las ecuaciones. [24] Los dos contraejemplos conocidos de la conjetura de Dirac-Motzkin (que establece que cualquier arreglo -lineal tiene al menos puntos ordinarios) son ambos simpliciales. [25]

El gráfico dual de una disposición lineal tiene un nodo por celda y una arista que une cualquier par de celdas que comparten una arista de la disposición. Estos gráficos son cubos parciales , gráficos en los que los nodos pueden etiquetarse mediante vectores de bits de tal manera que la distancia del gráfico es igual a la distancia de Hamming entre etiquetas. En el caso de una disposición lineal, cada coordenada del etiquetado asigna 0 a los nodos de un lado de una de las líneas y 1 a los nodos del otro lado. [26] Los gráficos duales de disposiciones simpliciales se han utilizado para construir familias infinitas de cubos parciales 3-regulares , isomorfos a los gráficos de zonoedros simples . [27]

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

Multicuadrículas y mosaicos de rombos

El gráfico dual de una disposición de líneas simple puede representarse geométricamente como una colección de rombos , uno por vértice de la disposición, con lados perpendiculares a las líneas que se encuentran en ese vértice. Estos rombos pueden unirse para formar un mosaico de un polígono convexo en el caso de una disposición de un número finito de líneas, o de todo el plano en el caso de una disposición localmente finita con un número infinito de líneas. Esta construcción a veces se conoce como diagrama de Klee , en honor a una publicación de Rudolf Klee en 1938 que utilizó esta técnica. Sin embargo, no todos los mosaicos de rombos provienen de líneas de esta manera. [33]

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

Existen también tres arreglos simpliciales infinitos formados a partir de conjuntos de líneas paralelas. El teselado tetrakis cuadrado es un arreglo infinito de líneas que forman un teselado periódico que se asemeja a una multicuadrícula 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 el arreglo es simplicial en lugar de simple. Su dual es el teselado cuadrado truncado . De manera similar, el teselado triangular es un arreglo de línea simplicial infinito con tres familias paralelas, que tiene como dual el teselado hexagonal , y el teselado hexagonal bisectado es un arreglo de línea simplicial infinito con seis familias paralelas y dos espaciados de línea, dual del gran teselado rombitrihexagonal . Estos tres ejemplos provienen de tres grupos de reflexión afines en el plano euclidiano, sistemas de simetrías basados ​​en la reflexión a través de cada línea en estos arreglos. [35]

Algoritmos

Construir un arreglo significa, dada como entrada una lista de las líneas en el arreglo, calcular una representación de los vértices, aristas y celdas del arreglo junto con las adyacencias entre estos objetos, por ejemplo como una lista de aristas doblemente conectadas . Debido al teorema de zona, los arreglos pueden construirse eficientemente mediante un algoritmo incremental que agrega una línea a la vez al arreglo de las líneas agregadas previamente: cada nueva línea puede agregarse en un tiempo proporcional a su zona, lo que resulta en un tiempo de construcción total de . [7] Sin embargo, los requisitos de memoria de este algoritmo son altos, por lo que puede ser más conveniente informar todas las características de un arreglo mediante un algoritmo que no mantenga todo el arreglo en la memoria a la vez. Esto nuevamente puede hacerse de manera eficiente, en tiempo y espacio , mediante una técnica algorítmica conocida como barrido topológico . [36] Calcular un arreglo de líneas exactamente requiere una precisión numérica varias veces mayor que la de las coordenadas de entrada: si una línea se especifica por dos puntos en ella, las coordenadas de los vértices del arreglo pueden necesitar cuatro veces más precisión que estos puntos de entrada. Por lo tanto, los geómetras computacionales también han estudiado algoritmos para construir arreglos de manera eficiente con precisión numérica limitada. [37]

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

Marc van Kreveld sugirió el problema algorítmico de calcular los caminos más cortos entre los vértices en una disposición de líneas, donde los caminos están restringidos a seguir los bordes de la disposición, más rápidamente que el tiempo cuadrático que tomaría aplicar un algoritmo de camino más corto a todo el gráfico de la disposición. [42] Se conoce un algoritmo de aproximación , [43] y el problema se puede resolver de manera eficiente para líneas que caen en un pequeño número de familias paralelas (como es típico para las cuadrículas de calles urbanas), [44] pero el problema general permanece abierto.

Disposiciones de líneas no euclidianas

Una disposición pseudolineal es una familia de curvas que comparten propiedades topológicas similares con una disposición lineal. [45] Estas pueden definirse de manera más simple en el plano proyectivo como curvas cerradas simples , dos de las cuales se encuentran en un único punto de cruce. [46] Se dice que una disposición pseudolineal es extensible si es combinatoriamente equivalente a una disposición lineal. Determinar la extensibilidad es una tarea computacional difícil: es completo para la teoría existencial de los números reales distinguir las disposiciones extensibles de las no extensibles. [47] Toda disposición de un número finito de pseudolíneas puede extenderse de modo que se conviertan en líneas en una "extensión", un tipo de geometría de incidencia no euclidiana en la que cada dos puntos de un plano topológico están conectados por una única línea (como en el plano euclidiano) pero en la que otros axiomas de la geometría euclidiana pueden no aplicarse. [48]

Otro tipo de geometría no euclidiana es el plano hiperbólico , y también se han estudiado los arreglos de líneas hiperbólicas en esta geometría. [49] Cualquier conjunto finito de líneas en el plano euclidiano tiene un arreglo combinatoriamente equivalente en el plano hiperbólico (por ejemplo, encerrando los vértices del arreglo por un círculo grande e interpretando el interior del círculo como un modelo de Klein del plano hiperbólico). Sin embargo, los pares de líneas paralelas (que no se cruzan) están menos restringidos en arreglos de líneas hiperbólicas que en el plano euclidiano: en particular, la relación de ser paralelas es una relación de equivalencia para líneas euclidianas pero no para líneas hiperbólicas. [50] El gráfico de intersección de las líneas en un arreglo hiperbólico puede ser un gráfico circular arbitrario . El concepto correspondiente a los arreglos de líneas hiperbólicas para pseudolíneas es un arreglo de pseudolínea débil , [51] una familia de curvas que tienen las mismas propiedades topológicas que las líneas [52] tales que dos curvas cualesquiera en la familia se encuentran en un único punto de cruce o no tienen intersección. [51]

Véase también

Notas

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

Referencias

Enlaces externos