El teorema de empaquetamiento de círculos (también conocido como teorema de Koebe-Andreev-Thurston ) describe las posibles relaciones de tangencia entre círculos en el plano cuyos interiores son disjuntos. Un empaquetamiento circular es una colección conectada de círculos (en general, en cualquier superficie de Riemann ) cuyos interiores están separados. La gráfica de intersección de un embalaje circular es la gráfica que tiene un vértice para cada círculo y una arista para cada par de círculos que son tangentes . Si el empaquetamiento del círculo está en el plano o, de manera equivalente, en la esfera, entonces su gráfico de intersección se llama gráfico de moneda ; De manera más general, los gráficos de intersección de objetos geométricos interiores disjuntos se denominan gráficos de tangencia o gráficos de contacto . Los gráficos de monedas siempre son conectados, simples y planos . El teorema del empaquetado circular establece que estos son los únicos requisitos para que un gráfico sea un gráfico de monedas:
Teorema de empaquetamiento circular : para cada gráfico plano simple conectado G hay un empaquetamiento circular en el plano cuyo gráfico de intersección es ( isomorfo a ) G.
Un gráfico plano máximo G es un gráfico plano simple finito al que no se pueden agregar más aristas preservando la planaridad. Un gráfico de este tipo siempre tiene una incrustación plana única, en la que cada cara de la incrustación (incluida la cara exterior) es un triángulo. En otras palabras, todo gráfico plano máximo G es el esqueleto 1 de un complejo simplicial que es homeomorfo a la esfera. El teorema del empaquetamiento de círculos garantiza la existencia de un empaquetamiento de círculos con un número finito de círculos cuyo gráfico de intersección es isomorfo a G. Como lo establece más formalmente el siguiente teorema, cada gráfico plano máximo puede tener como máximo un empaquetamiento.
Teorema de Koebe-Andreev-Thurston : si G es un gráfico plano máximo finito, entonces el empaque circular cuyo gráfico de tangencia es isomorfo a G es único, hasta transformaciones de Möbius y reflexiones en líneas.
Thurston observa que esta unicidad es consecuencia del teorema de rigidez de Mostow . Para ver esto, representemos G mediante un empaquetamiento circular. Entonces, el plano en el que se empaquetan los círculos puede verse como el límite de un modelo de semiespacio para el espacio hiperbólico tridimensional ; Desde esta perspectiva, cada círculo es el límite de un plano dentro del espacio hiperbólico. Se puede definir de esta manera un conjunto de planos disjuntos a partir de los círculos del empaque, y un segundo conjunto de planos disjuntos definidos por los círculos que circunscriben cada espacio triangular entre tres de los círculos del empaque. Estos dos conjuntos de planos se encuentran en ángulo recto y forman los generadores de un grupo de reflexión cuyo dominio fundamental puede verse como una variedad hiperbólica . Por la rigidez de Mostow, la estructura hiperbólica de este dominio está determinada de forma única, hasta la isometría del espacio hiperbólico; estas isometrías, cuando se ven en términos de sus acciones en el plano euclidiano en el límite del modelo de semiplano, se traducen en transformaciones de Möbius. [1]
También hay una prueba más elemental de la misma propiedad de unicidad, basada en la existencia de un valor máximo en cualquier conjunto finito y en la observación de que, en el triángulo que conecta los centros de tres círculos mutuamente tangentes, el ángulo formado en el centro de uno de los círculos es monótono decreciente en su radio y monótono creciente en los otros dos radios. Dados dos empaquetamientos para el mismo gráfico , se pueden aplicar reflexiones y transformaciones de Möbius para hacer que los círculos exteriores en estos dos empaquetamientos se correspondan entre sí y tengan los mismos radios. Entonces, sea un vértice interior para el cual los círculos en los dos empaquetamientos tengan tamaños lo más separados posible: es decir, elija maximizar la relación de los radios de sus círculos en los dos empaquetamientos. Para cada cara triangular que contiene , se deduce que el ángulo en el centro del círculo del primer empaque es menor o igual que el ángulo del segundo empaque, siendo posible la igualdad sólo cuando los otros dos círculos que forman el triángulo tienen la misma misma proporción de radios en los dos empaquetamientos. Pero la suma de los ángulos de todos estos triángulos que rodean el centro del triángulo debe estar en ambos empaquetamientos, por lo que todos los vértices vecinos deben tener la misma proporción que él mismo. Al aplicar el mismo argumento a estos otros círculos, se deduce que todos los círculos en ambos empaquetamientos tienen la misma proporción. Pero los círculos exteriores se han transformado para tener una proporción uno, por lo que los dos empaquetamientos tienen radios idénticos para todos los círculos.
Un mapa conforme entre dos conjuntos abiertos en el plano o en un espacio de dimensiones superiores es una función continua de un conjunto al otro que preserva los ángulos entre dos curvas cualesquiera. El teorema de mapeo de Riemann , formulado por Bernhard Riemann en 1851, establece que, para dos discos topológicos abiertos cualesquiera en el plano, existe un mapa conforme de un disco al otro. Los mapeos conformes tienen aplicaciones en la generación de mallas , proyección de mapas y otras áreas. Sin embargo, no siempre es fácil construir un mapeo conforme entre dos dominios dados de manera explícita. [2]
En la conferencia de Bieberbach en 1985, William Thurston conjeturó que los empaquetamientos circulares podrían usarse para aproximar mapeos conformes. Más precisamente, Thurston utilizó empaquetamientos circulares para encontrar un mapeo conforme desde un disco abierto arbitrario A al interior de un círculo; el mapeo de un disco topológico A a otro disco B podría entonces encontrarse componiendo el mapa de A a un círculo con el inverso del mapa de B a un círculo. [2]
La idea de Thurston era empaquetar círculos de algún radio pequeño r en una teselación hexagonal del plano, dentro de la región A , dejando una región estrecha cerca del límite de A , de ancho r , donde no caben más círculos de este radio. Luego construye un gráfico plano máximo G a partir del gráfico de intersección de los círculos, junto con un vértice adicional adyacente a todos los círculos en el límite del embalaje. Según el teorema de empaquetamiento de círculos, este gráfico plano se puede representar mediante un empaquetamiento de círculos C en el que todos los bordes (incluidos los que inciden en el vértice del límite) están representados por tangencias de círculos. Los círculos del embalaje de A corresponden uno por uno con los círculos de C , excepto el círculo límite de C que corresponde al límite de A. Esta correspondencia de círculos se puede utilizar para construir una función continua de A a C en la que cada círculo y cada espacio entre tres círculos se asigna de un empaque al otro mediante una transformación de Möbius . Thurston conjeturó que, en el límite cuando el radio r se acerca a cero, las funciones de A a C construidas de esta manera se aproximarían a la función conforme dada por el teorema de mapeo de Riemann. [2]
La conjetura de Thurston fue probada por Rodin y Sullivan (1987). Más precisamente, demostraron que, cuando n tiende al infinito, la función f n determinada utilizando el método de Thurston a partir de empaquetamientos hexagonales de círculos de radio 1/ n converge uniformemente en subconjuntos compactos de A a un mapa conforme de A a C. [2]
A pesar del éxito de la conjetura de Thurston, las aplicaciones prácticas de este método se han visto obstaculizadas por la dificultad de calcular los empaquetamientos de círculos y por su tasa de convergencia relativamente lenta. [3] Sin embargo, tiene algunas ventajas cuando se aplica a dominios no simplemente conectados y al seleccionar aproximaciones iniciales para técnicas numéricas que calculan mapeos de Schwarz-Christoffel , una técnica diferente para el mapeo conforme de dominios poligonales . [2]
Hay muchas demostraciones conocidas del teorema del empaquetamiento circular. La prueba original de Paul Koebe se basa en su teorema de uniformización conforme que dice que un dominio plano finitamente conexo es conformemente equivalente a un dominio circular. Se conocen varias pruebas topológicas diferentes. La demostración de Thurston se basa en el teorema del punto fijo de Brouwer . Como estudiante de posgrado, Oded Schramm fue supervisado por Thurston en la Universidad de Princeton . Como relata Rohde (2011, p. 1628), hay una "descripción poética" en la disertación de Schramm de cómo se puede deducir la existencia del empaquetamiento circular a partir del teorema del punto fijo: "Uno puede simplemente ver al terrible monstruo balanceando sus brazos en pura rabia". , los tentáculos provocan un espantoso silbido al frotarse unos contra otros." También hay una prueba que utiliza una variante discreta del método de Perron para construir soluciones al problema de Dirichlet . [4] Yves Colin de Verdière demostró la existencia del empaquetamiento circular como minimizador de una función convexa en un determinado espacio de configuración. [5]
El teorema del empaquetado circular es una herramienta útil para estudiar diversos problemas de geometría plana, asignaciones conformes y gráficos planos. De esta manera se ha obtenido una demostración alternativa del teorema del separador plano , originalmente debida a Lipton y Tarjan [6] . [7] Otra aplicación del teorema del empaquetado circular es que los límites insesgados de los gráficos planos de grados acotados son casi con seguridad recurrentes. [8] Otras aplicaciones incluyen implicaciones para el tiempo de cobertura. [9] y estimaciones para el valor propio más grande de gráficos de género acotado . [10]
En el dibujo de gráficos , el empaquetado circular se ha utilizado para encontrar dibujos de gráficos planos con resolución angular limitada [11] y con número de pendiente acotado . [12] El teorema de Fáry , de que todo gráfico que se puede dibujar sin cruces en el plano usando aristas curvas también se puede dibujar sin cruces usando aristas de segmentos de línea recta , se sigue como un simple corolario del teorema de empaquetamiento de círculos: colocando vértices en los centros de los círculos y trazando aristas rectas entre ellos se obtiene una incrustación plana y rectilínea.
Una forma más fuerte del teorema de empaquetamiento de círculos afirma que cualquier gráfico poliédrico y su gráfico dual pueden representarse mediante dos empaquetamientos de círculos, de modo que los dos círculos tangentes que representan un borde del gráfico primario y los dos círculos tangentes que representan el dual del mismo borde siempre tienen sus tangencias forman ángulos rectos entre sí en el mismo punto del plano. Un empaquetamiento de este tipo se puede utilizar para construir un poliedro convexo que represente el gráfico dado y que tenga una media esfera , una esfera tangente a todas las aristas del poliedro . Por el contrario, si un poliedro tiene una media esfera, entonces los círculos formados por las intersecciones de la esfera con las caras del poliedro y los círculos formados por los horizontes de la esfera vistos desde cada vértice del poliedro forman un empaquetamiento dual de este tipo.
Collins y Stephenson (2003) describen un algoritmo de relajación numérica para encontrar empaquetamientos circulares, basado en ideas de William Thurston . La versión del problema de empaquetamiento de círculos que resuelven toma como entrada un gráfico plano, en el que todas las caras internas son triángulos y cuyos vértices externos han sido etiquetados con números positivos. Produce como salida un empaquetamiento circular cuyas tangencias representan el gráfico dado, y para el cual los círculos que representan los vértices externos tienen los radios especificados en la entrada. Como sugieren, la clave del problema es calcular primero los radios de los círculos en el embalaje; una vez conocidos los radios, no es difícil calcular las posiciones geométricas de los círculos. Comienzan con un conjunto de radios tentativos que no corresponden a un embalaje válido y luego realizan repetidamente los siguientes pasos:
Cada uno de estos pasos se puede realizar con cálculos trigonométricos simples y, como sostienen Collins y Stephenson, el sistema de radios converge rápidamente a un punto fijo único para el cual todos los ángulos que lo cubren son exactamente 2π. Una vez que el sistema ha convergido, los círculos se pueden colocar uno a la vez, utilizando en cada paso las posiciones y radios de dos círculos vecinos para determinar el centro de cada círculo sucesivo.
Mohar (1993) describe una técnica iterativa similar para encontrar empaquetamientos simultáneos de un gráfico poliédrico y su dual, en el que los círculos duales están en ángulo recto con los círculos primarios. Demuestra que el método toma un tiempo polinómico en el número de círculos y en log 1/ε, donde ε es un límite en la distancia de los centros y radios del empaquetamiento calculado de aquellos en un empaquetamiento óptimo.
El teorema del empaquetado circular se generaliza a gráficas que no son planas. Si G es un gráfico que se puede incrustar en una superficie S , entonces hay una curvatura constante métrica de Riemann d en S y un círculo empaquetado en ( S , d ) cuyo gráfico de contactos es isomorfo a G. Si S es cerrado ( compacto y sin límite ) y G es una triangulación de S , entonces ( S , d ) y el empaquetamiento son únicos hasta la equivalencia conforme. Si S es la esfera, entonces esta equivalencia depende de las transformaciones de Möbius; si es un toro, entonces la equivalencia depende de la escala por una constante e isometrías, mientras que si S tiene género al menos 2, entonces la equivalencia depende de las isometrías.
Otra generalización del teorema de empaquetamiento de círculos implica reemplazar la condición de tangencia con un ángulo de intersección específico entre círculos correspondientes a vértices vecinos. Una versión particularmente elegante es la siguiente. Supongamos que G es un gráfico plano finito de 3 conexos (es decir, un gráfico poliédrico ), entonces hay un par de empaquetamientos circulares, uno cuyo gráfico de intersección es isomorfo a G , otro cuyo gráfico de intersección es isomorfo al dual plano de G. , y para cada vértice en G y cara adyacente a él, el círculo en el primer empaque correspondiente al vértice se cruza ortogonalmente con el círculo en el segundo empaque correspondiente a la cara. [13] Por ejemplo, al aplicar este resultado a la gráfica del tetraedro se obtiene, para cuatro círculos mutuamente tangentes cualesquiera, un segundo conjunto de cuatro círculos mutuamente tangentes, cada uno de los cuales es ortogonal a tres de los primeros cuatro. [14] Una generalización adicional, que reemplaza el ángulo de intersección con la distancia inversa , permite la especificación de empaquetaduras en las que se requiere que algunos círculos estén separados entre sí en lugar de cruzarse o ser tangentes. [15]
Otra variedad más de generalizaciones permite formas que no son círculos. Supongamos que G = ( V , E ) es un gráfico plano finito, y a cada vértice v de G le corresponde una forma , que es homeomorfa al disco unitario cerrado y cuyo límite es suave. Luego hay un empaquetamiento en el plano tal que si y sólo si y para cada uno el conjunto se obtiene traslazando y escalando. (Tenga en cuenta que en el teorema de empaquetamiento del círculo original, hay tres parámetros reales por vértice, dos de los cuales describen el centro del círculo correspondiente y uno describe el radio, y hay una ecuación por arista. Esto también se cumple en esta generalización .) Se puede obtener una prueba de esta generalización aplicando la prueba original de Koebe [16] y el teorema de Brandt [17] y Harrington [18] que establece que cualquier dominio finitamente conexo es conformemente equivalente a un dominio plano cuyos componentes límite tienen formas específicas. , hasta traducciones y escalado.
Los empaquetamientos circulares se estudiaron ya en 1910, en el trabajo de Arnold Emch sobre las espirales de Doyle en la filotaxis (las matemáticas del crecimiento de las plantas). [19] El teorema del empaquetamiento circular fue demostrado por primera vez por Paul Koebe . [16] William Thurston [1] redescubrió el teorema del empaquetamiento circular y señaló que se derivaba del trabajo de EM Andreev. Thurston también propuso un esquema para utilizar el teorema de empaquetamiento circular para obtener un homeomorfismo de un subconjunto propio del plano simplemente conectado en el interior del disco unitario. La conjetura de Thurston para empaquetamientos circulares es su conjetura de que el homeomorfismo convergerá al mapeo de Riemann cuando los radios de los círculos tiendan a cero. La conjetura de Thurston fue demostrada más tarde por Burton Rodin y Dennis Sullivan . [20] Esto llevó a una avalancha de investigaciones sobre extensiones del teorema de empaquetamiento de círculos, relaciones con asignaciones conformes y aplicaciones.
![{\displaystyle [v,u]\en E}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16c1d56679a8294977a7fe3a46540d080fec87e8)
