Disposición de líneas

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Subdivisión del avión por líneas

Un arreglo de línea simplicial (izquierda) y un arreglo de línea simple (derecha).

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

Definición

Intuitivamente, cualquier conjunto finito de líneas en el plano corta el plano en polígonos (celdas) bidimensionales, segmentos de línea o rayos unidimensionales y puntos de cruce de dimensión cero. Esto se puede formalizar matemáticamente clasificando los puntos del plano según en qué lado de cada línea se encuentran. Cada línea separa el plano en dos semiplanos abiertos, y cada punto del plano tiene tres posibilidades por línea: puede estar en cualquiera de estos dos semiplanos o puede estar en la propia línea. Se pueden considerar dos puntos equivalentes si tienen la misma clasificación respecto de todas las líneas. Esta es una relación de equivalencia, cuyas clases de equivalencia son subconjuntos de puntos equivalentes. Estos subconjuntos subdividen el plano en formas de los tres tipos siguientes:

El células o cámaras de la disposición son regiones bidimensionales no parte de ninguna línea. Forman los interiores de polígonos convexos atados o regiones convexas sin límites. 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.
El bordes o paneles de la disposición son regiones unidimensionales pertenecientes a una sola línea. Son los segmentos de línea abierta 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 otras líneas, estos son los componentes conectados de sus puntos no cortados.
El vertices de la disposición son puntos aislados pertenecientes 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.

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. , aunque en este caso las celdas ilimitadas pueden tener infinitos lados.

Complejidad de los acuerdos

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. Las características más sencillas de contar son los vértices, aristas y celdas:

Un arreglo con ${displaystyle n}$ las líneas tienen en la mayoría ${displaystyle n(n-1)/2}$ vértices (número triangular), uno por par de líneas de cruce. Este máximo se logra para arreglos simples, aquellos en los que cada dos líneas cruzan en un vértice que se descompone de todas las otras líneas. El número de vértices es menor cuando algunas líneas son paralelas, o cuando algunos vértices se cruzan por más de dos líneas.
Cualquier disposición se puede girar para evitar las líneas del eje-paralelo, sin cambiar su número de células. Cualquier arreglo sin líneas de eje-paralela tiene ${displaystyle n}$ Rayos infinitos hacia abajo, uno por línea. Estos rayos se separan ${displaystyle n+1}$ células del arreglo que no están abundadas en la dirección hacia abajo. Las células restantes tienen un vértice inferior único (de nuevo, porque no hay líneas de eje-paralelo). Para cada par de líneas, sólo puede haber una célula donde las dos líneas se encuentran en el vértice inferior, por lo que el número de células hacia abajo es en la mayoría del número de pares de líneas, ${displaystyle n(n-1)/2}$ . Añadiendo las células no abundadas y atadas, el número total de células en un arreglo puede ser a la mayoría ${displaystyle n(n+1)/2+1}$ . Estos son los números de la secuencia perezosa del gato.
El número de bordes del arreglo es a la mayoría ${displaystyle n^{2}}$ , como puede verse ya sea usando la característica de Euler para calcularla de los números de vértices y células, o observando que cada línea se divide en la mayoría ${displaystyle n}$ bordes por los otros ${displaystyle n-1}$ líneas. Una vez más, este límite peor se logra para arreglos simples.

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

El zona of a línea ${displaystyle ell }$ en un arreglo de línea es la colección de células que tienen bordes pertenecientes a ${displaystyle ell }$ . El teorema de zona establece que el número total de bordes en las células de una sola zona es lineal. Más precisamente, el número total de bordes de las células pertenecientes a un solo lado de línea ${displaystyle ell }$ es a la mayoría ${displaystyle 5n-1}$ , y el número total de bordes de las células pertenecientes a ambos lados de ${displaystyle ell }$ es a la mayoría ${displaystyle lfloor 9.5nrfloor -1}$ . Más generalmente, la complejidad total de las células de un arreglo de línea que están intersectadas por cualquier curva convexa es ${displaystyle O(nalpha (n))}$ , Donde ${displaystyle alpha }$ denota la función inversa Ackermann, como se puede mostrar utilizando secuencias Davenport–Schinzel. La suma de cuadrados de complejidades celulares en un arreglo es ${displaystyle O(n^{2})}$ , como se puede mostrar resumiendo las zonas de todas las líneas.
El ${displaystyle k}$ -nivel de un arreglo es la cadena poligonal formada por los bordes que tienen exactamente ${displaystyle k}$ otras líneas directamente debajo de ellas. El ${displaystyle leq k}$ - nivel es la parte del acuerdo debajo del ${displaystyle k}$ - nivel. Encontrar límites superiores e inferiores para la complejidad de un ${displaystyle k}$ - nivel sigue siendo un problema abierto importante en la geometría discreta. El mejor borde superior es ${displaystyle O(nk^{1/3})}$ , mientras que el mejor límite inferior es ${displaystyle n2^{Omega ({sqrt {log k}})}}$ . En cambio, la máxima complejidad de la ${displaystyle leq k}$ - nivel es conocido Ser ${displaystyle Theta (nk)}$ . A ${displaystyle k}$ - nivel es un caso especial de un camino monotono en un arreglo; es decir, una secuencia de bordes que intersecte cualquier línea vertical en un solo punto. Sin embargo, los caminos monotonales pueden ser mucho más complicados que ${displaystyle k}$ - niveles: existen arreglos y caminos monotonales en estos arreglos donde el número de puntos en los que el camino cambia la dirección es ${displaystyle n^{2-o(1)}}$ .
Aunque una sola célula en un acuerdo puede ser atada por todos ${displaystyle n}$ líneas, no es posible en general ${displaystyle m}$ diferentes células a todas ${displaystyle n}$ líneas. Más bien, la complejidad total de ${displaystyle m}$ células a la mayoría ${displaystyle Theta (m^{2/3}n^{2/3}+n)}$ , casi el mismo límite que ocurre en el teorema de Szemerédi-Trotter en incidencias de línea de punto en el plano. Una simple prueba de ello es la desigualdad del número de cruce: si ${displaystyle m}$ las células tienen un total ${displaystyle x+n}$ bordes, uno puede formar un gráfico con ${displaystyle m}$ nodos (uno por célula) y ${displaystyle x}$ bordes (uno por par de células consecutivas en la misma línea). Los bordes de este gráfico se pueden dibujar como curvas que no cruzan dentro de las células correspondientes a sus puntos finales, y luego siguen las líneas del arreglo. Por lo tanto, hay ${displaystyle O(n^{2})}$ cruces en este dibujo. Sin embargo, por la desigualdad del número de cruce, hay ${displaystyle Omega (x^{3}/m^{2})}$ cruces. Para satisfacer ambos límites, ${displaystyle x}$ Debe Ser ${displaystyle O(m^{2/3}n^{2/3})}$ .

Disposiciones proyectivas y dualidad proyectiva

Es conveniente estudiar la disposición de las líneas en el plano proyectivo ya que cada par de líneas tiene un punto de cruce. La disposición de las líneas no se puede definir utilizando los lados de las líneas, porque una línea en el plano proyectivo no separa el plano en dos lados distintos. Todavía 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 dos o más las líneas se cruzan. 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.

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 puntos finitamente Muchas líneas con más de un vértice tienen un punto ordinario, un vértice donde solo se cruzan dos líneas. La primera prueba 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.

Triángulos 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á delimitada por exactamente tres aristas. Melchor estudió por primera vez los arreglos simples. Se conocen tres familias infinitas de disposiciones lineales simpliciales:

A casi-pencil consistente en ${displaystyle n-1}$ líneas a través de un solo punto, junto con una única 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 la simetría de un polígono uniforme regular, 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. Como escribe Branko Grünbaum, los arreglos simpliciales "aparecen como ejemplos o contraexamples en muchos contextos de geometría combinatoria y sus aplicaciones". Por ejemplo, Artés, Grünbaum & Llibre (1998) utilizan arreglos simpliciales para construir contraexamples 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. Los dos contraexamples conocidos a la conjetura Dirac-Motzkin (que declara que cualquier ${displaystyle n}$ - Línea por lo menos ${displaystyle n/2}$ puntos ordinarios) son ambos simplicial.

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. 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.

Un arreglo con el número mínimo de triángulos de acuerdo con el triángulo de Roberts teorema

triángulos de Kobon en un arreglo de 17 líneas

También es de interés estudiar el número extremal de células triangulares en arreglos que pueden no ser necesariamente simpliciales. Cualquier arreglo en el plano proyectivo debe tener al menos ${displaystyle n}$ triángulos. Todo arreglo que sólo tiene ${displaystyle n}$ Los triángulos deben ser simples. Para Euclidean en lugar de acuerdos de proyecto, el número mínimo de triángulos es ${displaystyle n-2}$ , por el teorema triángulo de Roberts. Se sabe que el número máximo posible de rostros triangulares en un arreglo simple es superior a los límites ${displaystyle n(n-1)/3}$ y inferior por ${displaystyle n(n-3)/3}$ ; el límite inferior se logra por ciertos subconjuntos de las diagonales de un regular ${displaystyle 2n}$ - Vete. Para los arreglos no simples el número máximo de triángulos es similar pero más estrechamente ligado. El problema del triángulo de Kobon estrechamente relacionado pide el número máximo de triángulos finitos no superpuestos en un arreglo en el plano Euclideano, sin contar las caras sin límites que podrían formar triángulos en el plano proyectivo. Para algunos pero no todos los valores de ${displaystyle n}$ , ${displaystyle n(n-2)/3}$ triángulos son posibles.

Múltiples rejillas y mosaicos de rombos

La gráfica dual de un arreglo lineal simple se puede representar geométricamente como una colección de rombos, uno por vértice del arreglo, 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 finito de líneas. Esta construcción se conoce a veces como diagrama de Klee, debido 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.

de Bruijn (1981) investigó casos especiales de esta construcción en los que el arreglo de línea consta de ${displaystyle k}$ conjuntos de líneas paralelas igualmente espaciadas. Para dos familias perpendiculares de líneas paralelas esta construcción simplemente da el revestimiento cuadrado familiar del plano, y para tres familias de líneas en ángulos de 120 grados uno del otro (los mismos que forman una baldosa trihexagonal) esto produce el revestimiento de rombille. Sin embargo, para más familias de líneas esta construcción produce revestimientos aperódicos. En particular, para cinco familias de líneas en ángulos iguales entre sí (o, como de Bruijn llama este arreglo, un pentagrid) produce una familia de azulejos que incluyen la versión rhombic de los azulejos Penrose.

Tetrakis azulejo cuadrado

Tiling triangular

Tiling hexagonal bisecado

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. embaldosado. 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.

Algoritmos

Construcción un arreglo significa, dado como entrada una lista de las líneas en el arreglo, computar una representación de los vértices, bordes y células del arreglo junto con las adyacencias entre estos objetos, por ejemplo como una lista doble de bordes conectados. Debido al teorema de zona, los arreglos pueden ser construidos eficientemente por un algoritmo incremental que agrega una línea a la vez a la disposición de las líneas previamente agregadas: cada nueva línea se puede añadir en tiempo proporcional a su zona, dando lugar a un tiempo total de construcción de ${displaystyle O(n^{2})}$ . Sin embargo, los requisitos de memoria de este algoritmo son altos, por lo que puede ser más conveniente informar todas las características de un arreglo por un algoritmo que no mantiene todo el arreglo en la memoria a la vez. Esto puede hacerse de nuevo de manera eficiente, en tiempo ${displaystyle O(n^{2})}$ y espacio ${displaystyle O(n)}$ , por una técnica algoritmo conocida como barrido topológico. Computar un arreglo de línea requiere exactamente 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, geométricos computacionales también han estudiado algoritmos para construir arreglos eficientemente con precisión numérica limitada.

Además, los investigadores han estudiado algoritmos eficientes para construir porciones más pequeñas de un arreglo, como zonas, ${displaystyle k}$ - niveles, o el conjunto de células que contienen un determinado conjunto de puntos. El problema de encontrar el acuerdo vértice con la mediana ${displaystyle x}$ -coordinado surge (en forma dual) en estadísticas robustas como el problema de computar el estimador Theil-Sen de un conjunto de puntos.

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 gráfico de disposición completo. Se conoce un algoritmo de aproximación 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), pero el problema general permanece abierto.

Disposiciones de líneas no euclidianas

Un arreglo pseudolín no estreñible de nueve pseudolíneas. (Todos los arreglos de menos de nueve pseudolines son estirables.) El teorema hexágono de Per Pappus, este arreglo no se puede realizar en un plano proyectivo sobre cualquier campo.

Un arreglo de línea hiperbólica combinatorialmente equivalente a un diagrama de acordes utilizado por Ageev (1996) para mostrar que los gráficos círculo libres de triángulo a veces pueden necesitar 5 colores.

Una disposición de pseudolíneas es una familia de curvas que comparten propiedades topológicas similares con una disposición de líneas. Éstas se pueden definir de forma más sencilla en el plano proyectivo como curvas cerradas simples de las cuales dos de ellas se encuentran en un único punto de cruce. Se dice que una disposición de pseudolíneas es estirable si es combinatoriamente equivalente a una disposición de líneas. 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. 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.

Otro tipo de geometría no euclidiana es el plano hiperbólico, y También se han estudiado disposiciones de 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, 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. 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ébiles, una familia de curvas que tienen las mismas propiedades topológicas que las líneas, de modo que dos curvas cualesquiera de la familia se encuentran en un solo punto de cruce o tienen sin intersección.

Contenido relacionado

Más resultados...