El teorema de empaquetamiento de círculos (también conocido como el teorema de Koebe-Andreev-Thurston ) describe las posibles relaciones de tangencia entre círculos en el plano cuyos interiores son disjuntos. Un empaque 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 empaque de círculos es la gráfica que tiene un vértice para cada círculo y un borde para cada par de círculos que son tangentes . Si el empaque 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, las gráficas de intersección de objetos geométricos disjuntos en el interior se denominan gráficas de tangencia o gráficas de contacto . Los gráficos de monedas siempre están conectados, son simples y planos . El teorema del empaquetamiento circular establece que estos son los únicos requisitos para que un gráfico sea un gráfico de moneda:
Circle embalaje teorema : Por cada sencillo conectado planar gráfico G hay un embalaje círculo en el plano cuya intersección gráfica es ( isomorfo a) G .
Unicidad
Un gráfico plano máximo G es un gráfico plano simple finito al que no se pueden añadir más aristas conservando 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, cada grafo plano máximo G es el esqueleto 1 de un complejo simplicial que es homeomorfo a la esfera. El círculo de embalaje teorema garantiza la existencia de un círculo de embalaje con un número finito de círculos cuya gráfica intersección es isomorfo a G . Como el siguiente teorema establece de manera más formal, cada grafo 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 empaquetamiento circular cuyo gráfico de tangencia es isomorfo a G es único, hasta las transformaciones de Möbius y las reflexiones en las líneas.
Thurston [1] observa que esta singularidad es una consecuencia del teorema de rigidez de Mostow . Para ver esto, sea G representado por un círculo de empaquetamiento. 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 ; con esta vista, cada círculo es el límite de un plano dentro del espacio hiperbólico. De esta manera, se puede definir 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 ángulos rectos y forman los generadores de un grupo de reflexión cuyo dominio fundamental puede verse como una variedad hiperbólica . Por 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.
También hay una prueba más elemental de la misma propiedad de unicidad, basada en el principio máximo 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ótona aumentando en los otros dos radios. Dados dos empaques para el mismo gráfico G , se pueden aplicar reflexiones y transformaciones de Möbius para hacer que los círculos exteriores en estos dos empaques se correspondan entre sí y tengan los mismos radios. Entonces, sea v un vértice interior de G para el cual los círculos en los dos empaques tienen tamaños lo más separados posible: es decir, elija v para maximizar la relación r 1 / r 2 de los radios de sus círculos en el dos envases. Para cada cara triangular de G que contiene v , se deduce que el ángulo en el centro del círculo para v en el primer empaque es menor o igual que el ángulo en el segundo empaque, siendo posible la igualdad solo cuando los otros dos círculos forman el triángulo tienen la misma relación r 1 / r 2 de radios en los dos empaques. Pero la suma de los ángulos de todos estos triángulos que rodean el centro del triángulo debe ser 2π en ambos empaquetamientos, por lo que todos los vértices vecinos av deben tener la misma razón que v . Al aplicar el mismo argumento a estos otros círculos sucesivamente, se deduce que todos los círculos en ambos envases tienen la misma proporción. Pero los círculos exteriores se han transformado para tener una relación 1, por lo que r 1 / r 2 = 1 y los dos empaques tienen radios idénticos para todos los círculos.
Relaciones con la teoría del mapeo conforme
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 conserva 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 conformales 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 forma explícita. [2]
En la conferencia de Bieberbach en 1985, William Thurston conjeturó que los empaques circulares podrían usarse para aproximar los mapeos conformes. Más precisamente, Thurston usó empaquetaduras circulares para encontrar un mapeo conforme desde un disco abierto arbitrario A hasta el interior de un círculo; el mapeo de un disco topológico A a otro disco B se podría encontrar componiendo el mapa de A a un círculo con la inversa del mapa de B a un círculo. [2]
La idea de Thurston era empaquetar círculos de un pequeño radio 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 una gráfica plana máxima G a partir de la gráfica de intersección de los círculos, junto con un vértice adicional adyacente a todos los círculos en el límite del empaque. Mediante el teorema del empaquetamiento de círculos, este gráfico plano se puede representar mediante un empaquetamiento de círculos C en el que todas las aristas (incluidas las incidentes al vértice del límite) están representadas por tangencias de círculos. Los círculos de la empaquetadura de A corresponden uno a uno con los círculos de C , excepto para 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 mapea de un empaquetamiento al otro mediante una transformación de Möbius . Thurston conjeturó que, en el límite cuando el radio r se aproxima a cero, las funciones de A a C construidas de esta manera se acercarí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, como n tiende a infinito, la función f n determina utilizando el método de Thurston de envases hexagonales de radio-1 / n círculos converge uniformemente sobre subconjuntos compactos de A a un mapa conformal 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 circulares y por su tasa de convergencia relativamente lenta. Sin embargo, tiene algunas ventajas cuando se aplica a dominios no simplemente conectados y en la selección de aproximaciones iniciales para técnicas numéricas que calculan mapeos de Schwarz-Christoffel , una técnica diferente para mapeo conforme de dominios poligonales . [2]
Pruebas
Hay muchas pruebas conocidas del teorema del empaquetamiento circular. La demostración original de Paul Koebe se basa en su teorema de uniformización conforme que dice que un dominio plano finitamente conectado es conforme de manera equivalente a un dominio circular. Hay varias pruebas topológicas diferentes que se conocen. 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 la existencia del empaquetamiento de círculos puede deducirse del teorema del punto fijo: "Uno puede simplemente ver al terrible monstruo balanceando sus brazos con 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 . [3] 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. [4]
Aplicaciones
El teorema del empaquetamiento circular es una herramienta útil para estudiar varios problemas en geometría plana, mapeos conformes y gráficas planas. De esta forma se ha obtenido una elegante demostración del teorema del separador plano , originalmente debida a Lipton y Tarjan [5] . [6] Otra aplicación del teorema del empaquetamiento circular es que los límites insesgados de los gráficos planos de grados acotados son casi con seguridad recurrentes. [7] Otras aplicaciones incluyen implicaciones para el tiempo de cobertura . [8] y estimaciones para el mayor valor propio de los gráficos de género acotado . [9]
En el dibujo de gráficos , el empaquetado circular se ha utilizado para encontrar dibujos de gráficos planos con resolución angular acotada [10] y con número de pendiente acotado . [11] El teorema de Fáry , que todo gráfico que se puede dibujar sin cruces en el plano usando bordes curvos también se puede dibujar sin cruces usando bordes de segmento de línea recta , sigue como un corolario simple del teorema de empaquetado circular: colocando vértices en los centros de los círculos y dibujando bordes rectos entre ellos, se obtiene una incrustación plana en línea recta.
Una forma más fuerte del teorema del empaquetamiento circular afirma que cualquier gráfico poliédrico y su gráfico dual se pueden representar mediante dos empaques circulares, de modo que los dos círculos tangentes que representan un borde de gráfico primario y los dos círculos tangentes que representan el dual del mismo borde siempre tienen sus tangencias en ángulo recto entre sí en el mismo punto del plano. Se puede usar un empaque de este tipo para construir un poliedro convexo que represente el gráfico dado y que tenga una esfera media , una esfera tangente a todos los bordes del poliedro . Por el contrario, si un poliedro tiene una esfera media, 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 como se ve desde cada vértice del poliedro forman un empaquetamiento dual de este tipo.
Aspectos algorítmicos
Collins y Stephenson (2003) describen un algoritmo de relajación numérico para encontrar empaquetaduras de círculos, 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 para el cual los vértices externos se han etiquetado con números positivos. Produce como salida un empaquetado 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 empaque; una vez que se conocen los radios, las posiciones geométricas de los círculos no son difíciles de calcular. Comienzan con un conjunto de radios tentativos que no corresponden a un empaque válido y luego realizan repetidamente los siguientes pasos:
- Elija un vértice interno v del gráfico de entrada.
- Calcule el ángulo total θ que sus k círculos vecinos cubrirían alrededor del círculo para v , si los vecinos se colocaran tangentes entre sí y al círculo central usando sus radios tentativos.
- Determine un radio representativo r para los círculos vecinos, de modo que k círculos de radio r den el mismo ángulo de cobertura θ que dan los vecinos de v .
- Establezca el nuevo radio de v para que sea el valor para el cual k círculos de radio r darían un ángulo de cobertura de exactamente 2π.
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 que todos los ángulos de cobertura son exactamente 2π. Una vez que el sistema ha convergido, los círculos pueden colocarse uno a la vez, en cada paso utilizando las posiciones y los 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 forman ángulos rectos con los círculos primarios. Demuestra que el método toma polinomio de tiempo 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.
Generalizaciones
El teorema del empaquetamiento de círculos se generaliza a gráficos que no son planos. Si G es un gráfico que puede ser embebido en una superficie S , entonces no es una constante curvatura de Riemann métrica d en S y una empaquetadura de círculo en ( S , d ) cuyos contactos gráfica 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 de una constante e isometrías, mientras que si S tiene un género al menos 2, entonces la equivalencia depende de las isometrías.
Otra generalización del teorema del 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. Suponga que G es un gráfico plano finito de 3 conexiones (es decir, un gráfico poliédrico ), entonces hay un par de empaquetaduras 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 interseca ortogonalmente con el círculo en el segundo empaque correspondiente a la cara. [12] Por ejemplo, aplicar este resultado a la gráfica del tetraedro da, para cuatro círculos tangentes mutuos, un segundo conjunto de cuatro círculos mutuamente tangentes, cada uno de los cuales es ortogonal a tres de los cuatro primeros. [13] Una generalización adicional, reemplazando 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. [14]
Sin embargo, otra variedad de generalizaciones permite formas que no son círculos. Suponga que G = ( V , E ) es un gráfico plano finito, y a cada vértice v de G corresponde una forma, que es homeomorfo al disco unitario cerrado y cuyo límite es suave. Entonces hay un embalaje en el avión de tal manera que si y solo si y para cada el conjunto se obtiene de traduciendo y escalando. (Tenga en cuenta que en el teorema de empaquetamiento de círculos original, hay tres parámetros reales por vértice, dos de los cuales describen el centro del círculo correspondiente y uno de los cuales describe el radio, y hay una ecuación por borde. Esto también es válido en esta generalización .) Una prueba de esta generalización se puede obtener aplicando la prueba original de Koebe [15] y el teorema de Brandt [16] y Harrington [17] que establece que cualquier dominio finitamente conectado es conforme de manera equivalente a un dominio plano cuyos componentes de frontera tienen formas específicas. , hasta traducciones y escalado.
Historia
El teorema del empaquetamiento circular fue probado por primera vez por Paul Koebe . [15] 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 usar el teorema del empaquetamiento de círculos para obtener un homeomorfismo de un subconjunto adecuado simplemente conectado del plano en el interior del disco unitario. La conjetura de Thurston para empaquetaduras de círculos es su conjetura de que el homeomorfismo convergerá al mapeo de Riemann cuando los radios de los círculos tienden a cero. La conjetura de Thurston fue probada más tarde por Burton Rodin y Dennis Sullivan . [18] Esto condujo a una avalancha de investigaciones sobre las extensiones del teorema del empaquetamiento de círculos, las relaciones con los mapeos conformes y las aplicaciones.
Ver también
- Junta apolínea , un empaque infinito formado al llenar repetidamente huecos triangulares
- Empaque de círculos, arreglos densos de círculos sin tangencias especificadas
- Espirales Doyle , empaquetaduras circulares que representan infinitas gráficas planas de 6 regulares
- Círculos de Ford , un conjunto de círculos a lo largo de la recta numérica racional
- Gráfico de centavos , los gráficos de monedas cuyos círculos tienen radios iguales
- Lema de anillo , un límite en los tamaños de círculos adyacentes en un empaque
Notas
- ↑ a b Thurston (1978-1981) , Cap. 13.
- ↑ a b c d e Stephenson (1999) .
- ^ Beardon y Stephenson 1991 , Carter y Rodin 1992
- ^ Colin de Verdière 1991
- ^ Lipton y Tarjan (1979)
- ^ Miller y col. (1997)
- ^ Benjamini y Schramm (2001)
- ^ Jonnason y Schramm (2000)
- ↑ Kelner (2006)
- ^ Malitz y Papakostas (1994) .
- ^ Keszegh, Pach y Pálvölgyi (2011) .
- ^ Brightwell y Scheinerman (1993)
- ^ Coxeter, HSM (2006), "Una propiedad absoluta de cuatro círculos mutuamente tangentes", Geometrías no euclidianas , Matemáticas. Apl. (NY), 581 , Nueva York: Springer, págs. 109-114, doi : 10.1007 / 0-387-29555-0_5 , MR 2191243.
- ^ Bowers, Philip L .; Stephenson, Kenneth (2004), "8.2 Empaquetamientos de distancia inversora", Uniformización de dessins y mapas de Belyĭ mediante empaquetamiento circular , Memoirs of the American Mathematical Society, 170 , pp. 78-82, doi : 10.1090 / memo / 0805 , MR 2053391.
- ↑ a b Koebe (1936)
- ↑ Brandt (1980)
- ↑ Harrington (1982)
- ^ Rodin y Sullivan (1987)
Referencias
- Andreev, EM (1970), "Poliedros convexos en espacios Lobačevskiĭ", Mat. Sb. , Serie nueva, 81 (123): 445–478, MR 0259734.
- Beardon, Alan F .; Stephenson, Kenneth (1990), "El teorema de uniformización para empaquetaduras circulares" , Indiana Univ. Matemáticas. J. , 39 (4): 1383–1425, doi : 10.1512 / iumj.1990.39.39062
- Beardon, Alan F .; Stephenson, Kenneth (1991), "El lema de Schwarz-Pick para empaquetaduras circulares" , Illinois J. Math. , 35 (4): 577–606, doi : 10.1215 / ijm / 1255987673
- Andreev, EM (1970), "Poliedros convexos de volumen finito en el espacio Lobačevskiĭ", Mat. Sb. , Serie nueva, 83 (125): 256–260, MR 0273510.
- Benjamini, Itai ; Schramm, Oded (2001), "Recurrencia de límites de distribución de gráficos planos finitos" , Electronic Journal of Probability , 6 , doi : 10.1214 / EJP.v6-96 , MR 1873300 , S2CID 2862151.
- Brandt, M. (1980), "Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete", Bull. De la Soc. Des Sc. Et des Lettr. De Łódź , 30.
- Brightwell, Graham R .; Scheinerman, Edward R. (1993), "Representaciones de gráficos planos", SIAM J. Discrete Math. , 6 (2): 214–229, doi : 10.1137 / 0406017.
- Carter, Ithiel; Rodin, Burt (1992), "Un problema inverso para el empaquetamiento circular y el mapeo conforme" , Trans. Amer. Matemáticas. Soc. , 334 (2): 861–875, doi : 10.1090 / S0002-9947-1992-1081937-X
- Colin de Verdière, Yves (1991), "Une principe variaciónnel pour les empilements de cercles", Inventiones Mathematicae , 104 (1): 655–669, Bibcode : 1991InMat.104..655C , doi : 10.1007 / BF01245096 , S2CID 121028882.
- Collins, Charles R .; Stephenson, Kenneth (2003), "Un algoritmo de empaquetamiento circular", Geometría computacional. Teoría y aplicaciones , 25 (3): 233–256, doi : 10.1016 / S0925-7721 (02) 00099-8 , MR 1975216.
- Harrington, Andrew N. (1982), "Asignaciones conformales en dominios con formas de límites especificadas arbitrariamente", Journal d'Analyse Mathématique , 41 (1): 39–53, doi : 10.1007 / BF02803393 , S2CID 120752035
- Jonnason, Johan; Schramm, Oded (2000), "En el tiempo de cobertura de los gráficos planares" , Comunicaciones electrónicas en probabilidad , 5 : 85–90.
- Kelner, Jonathan A. (2006), "Partición espectral, límites de valores propios y empaquetaduras circulares para gráficos de géneros acotados", SIAM Journal on Computing , 35 (4): 882–902, doi : 10.1137 / S0097539705447244 , hdl : 1721.1 / 30169.
- Keszegh, Balázs; Pach, János ; Pálvölgyi, Dömötör (2011), "Dibujar gráficas planas de grado acotado con pocas pendientes", en Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Alemania, 21-24 de septiembre de 2010, Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Heidelberg: Springer, págs. 293–304 , arXiv : 1009.1315 , doi : 10.1007 / 978-3-642-18469-7_27 , MR 2781274 , S2CID 817874.
- Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. , 88 : 141–164.
- Lipton, Richard J .; Tarjan, Robert E. (1979), "Un teorema del separador para gráficas planas", SIAM Journal on Applied Mathematics , 36 (2): 177–189, CiteSeerX 10.1.1.104.6528 , doi : 10.1137 / 0136016.
- Malitz, Seth; Papakostas, Achilleas (1994), "Sobre la resolución angular de gráficos planos", SIAM Journal on Discrete Mathematics , 7 (2): 172-183, doi : 10.1137 / S0895480193242931 , MR 1271989.
- Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "Separadores para empaquetaduras de esferas y gráficos de vecinos más cercanos", J. ACM , 44 (1): 1–29, doi : 10.1145 / 256292.256294 , S2CID 17331739.
- Mohar, Bojan (1993), "Un algoritmo de empaquetamiento de círculo de tiempo polinomial", Matemáticas discretas , 117 (1-3): 257-263, doi : 10.1016 / 0012-365X (93) 90340-Y.
- Rodin, Burton ; Sullivan, Dennis (1987), "La convergencia de empaquetaduras circulares al mapeo de Riemann" , Journal of Differential Geometry , 26 (2): 349–360, doi : 10.4310 / jdg / 1214441375.
- Rohde, Steffen (2011), "Oded Schramm: del empaque circular al LES" , Ann. Probab. , 39 (5): 1621–1667, doi : 10.1214 / 10-AOP590
- Stephenson, Kenneth (1999), "La aproximación de estructuras conformes mediante el empaquetado circular" (PDF) , Métodos computacionales y teoría de funciones 1997 (Nicosia) , Ser. Aprox. Decompos., 11 , World Sci. Publ., River Edge, Nueva Jersey, págs. 551–582, MR 1700374.
- Stephenson, Ken (2003), "Empaquetado de círculos: un cuento matemático" (PDF) , Notices Amer. Matemáticas. Soc. , 50 : 1376–1388
- Stephenson, Ken (2005), Introducción al empaquetamiento de círculos, la teoría de funciones analíticas discretas , Cambridge: Cambridge University Press.
- Thurston, William (1985), El teorema del mapeo finito de Riemann , Charla invitada en el Simposio Internacional de la Universidad de Purdue con motivo de la prueba de la conjetura de Bieberbach..
- Thurston, William (1978-1981), La geometría y topología de tres variedades , notas de la conferencia de Princeton.
enlaces externos
- CirclePack (software gratuito para construir empaquetaduras circulares a partir de gráficos) y bibliografía de empaquetamiento circular de Kenneth Stephenson, Univ. de Tennessee