Théorème d'empilement de cercles

Le théorème d'empilement de cercles (aussi connu sous le nom de théorème de Koebe–Andreev–Thurston, et démontré par Paul Koebe et William Thurston) décrit les relations de tangence possibles entre des cercles dans le plan. Un empilement de cercles est une collection connexe de disques du plan (ou plus généralement de n'importe quelle surface de Riemann) dont les intérieurs sont disjoints. Le graphe d'intersection d'un empilement de cercles est le graphe ayant un sommet pour chaque cercle, et une arête pour chaque paire de cercles qui sont tangents. Si l'empilement de cercles est sur le plan ou sur la sphère, alors son graphe d'intersection est appelé un graphe de pièces ; plus généralement, les graphes d'intersection d'objets géométriques connectés, d'intérieurs disjoints sont appelés graphes de tangence ou graphes de contact. Les graphes de pièces sont toujours connexes, simples et planaires. Le théorème d'empilement de cercles affirme que ce sont les seules exigences pour qu'un graphe soit un graphe de pièces : pour tout graphe planaire simple et connexe G, il existe un empilement de cercles dans le plan dont le graphe d'intersection est isomorphe à G.

Un graphe planaire maximal G est un graphe planaire simple fini auquel aucune arête ne peut être ajoutée tout en préservant la planéité. Un tel graphe a toujours un unique plongement planaire, dans lequel chaque face du plongement (y compris la face extérieure) est un triangle. En d'autres termes, chaque graphe planaire maximal G est le 1-squelette d'un complexe simplicial qui est homéomorphe à la sphère. Le théorème d'empilement de cercles garantit l'existence d'un empilement (fini) de cercles dont le graphe d'intersection est isomorphe à G. Comme l'affirme l‘énoncé suivant de manière plus formelle, chaque graphe planaire maximal ne peut correspondre qu'à un seul empilement.

Théorème de Koebe–Andreev–Thurston : Si G est un graphe planaire simple et connexe, alors il existe un empilement de cercles dont le graphe de tangence est isomorphe à G, et si G est maximal (fini) cet empilement est unique, à des transformations de Möbius et des réflexions près.

Thurston observe que cette unicité est une conséquence du théorème de rigidité de Mostow (en). Pour voir cela, soit G un graphe représenté par un empilement de cercles. Alors le plan dans lequel les cercles sont empilés peut être vu comme la frontière d'un demi-espace de Poincaré modélisant l'espace hyperbolique tridimensionnel ; de ce point de vue, chaque cercle est la frontière (l'ensemble des points à l'infini) d'un plan de l'espace hyperbolique (modélisé par une demi-sphère). On peut définir un ensemble de plans disjoints (mais asymptotes) de cette manière à partir des cercles de l'empilement, et un second ensemble de plans disjoints défini par les cercles qui circonscrivent chaque triplet de cercles de l'empilement tangents deux à deux. Ces deux ensembles de plans se rencontrent à angle droit et forment les générateurs d'un groupe de réflexion dont le domaine fondamental peut être vu comme une variété hyperbolique. Par le théorème de Mostow, la structure hyperbolique de ce domaine est déterminée de manière unique à une isométrie de l'espace hyperbolique près ; les actions de ces isométries sur le plan euclidien frontière du demi-espace de Poincaré sont des transformations de Möbius^[1].

Une preuve plus élémentaire de cette propriété d'unicité est basée sur l'existence d'une valeur maximale dans tout ensemble fini et sur l'observation que, dans le triangle reliant les centres de trois cercles mutuellement tangents, l'angle formé au centre de l'un des cercles diminue de manière monotone par rapport à son rayon et augmente de manière monotone par rapport aux deux autres rayons. Étant donné deux empilements ayant le même graphe ${\displaystyle G}$, on peut appliquer des réflexions et des transformations de Möbius pour faire correspondre les cercles extérieurs de ces deux empilements et avoir les mêmes rayons. Ensuite, soit ${\displaystyle v}$ un sommet intérieur de ${\displaystyle G}$ pour lequel les cercles dans les deux empilements ont des tailles aussi éloignées que possible (autrement dit, on choisit ${\displaystyle v}$ pour maximiser le rapport ${\displaystyle r_{1}/r_{2}}$ des rayons de ces cercles dans les deux empilements). Pour chaque face triangulaire de ${\displaystyle G}$ contenant ${\displaystyle v}$, il en résulte que l'angle au centre du cercle pour ${\displaystyle v}$ dans le premier empilement est inférieur ou égal à l'angle dans le deuxième empilement, avec égalité possible seulement lorsque les deux autres cercles formant le triangle ont le même rapport ${\displaystyle r_{1}/r_{2}}$ des rayons dans les deux empilements. Mais la somme des angles de tous ces triangles entourant le centre du triangle doit être ${\displaystyle 2\pi }$ dans les deux empilements, donc tous les sommets voisins de ${\displaystyle v}$ doivent avoir le même rapport ${\displaystyle r_{1}/r_{2}}$ que ${\displaystyle v}$. En appliquant le même argument à ces autres cercles à leur tour, il en résulte que tous les cercles dans les deux empilements ont le même rapport de rayons. Mais les cercles extérieurs ont été transformés pour avoir le même rayon, donc ${\displaystyle r_{1}/r_{2}=1}$ et les deux empilements ont des rayons identiques pour tous les cercles.

Une transformation conforme entre deux ensembles ouverts dans le plan ou dans un espace de dimension supérieure est une fonction continue d'un ensemble à l'autre qui préserve les angles entre deux courbes quelconques. Le théorème de l'application conforme, formulé par Bernhard Riemann en 1851, affirme que, pour deux ouverts quelconques du plan homéomorphes à des disques ouverts, il existe une application conforme de l'un à l'autre. Les transformations conformes ont de nombreuses applications pratiques, mais il n'est pas toujours facile de construire une transformation conforme entre deux domaines donnés de manière explicite^[2].

Lors de la conférence de Bieberbach de 1985, William Thurston a conjecturé que les empilements de cercles pouvaient être utilisés pour approximer les transformations conformes. Plus précisément, Thurston a utilisé des empilements de cercles pour trouver une transformation conforme d'un disque ouvert arbitraire A à l'intérieur d'un cercle ; l'application d'un disque topologique A à un autre disque B pouvait alors être trouvée en composant l'application de A à un cercle avec l'inverse de l'application de B à un cercle^[2].

L'idée de Thurston était de placer des cercles d'un petit rayon r dans un pavage hexagonal du plan, dans la région A, en laissant une région étroite près de la frontière de A, de largeur r, où aucun autre cercle de ce rayon ne peut s'insérer. Il construit alors un graphe planaire maximal G à partir du graphe d'intersection des cercles, avec un sommet supplémentaire adjacent à tous les cercles à la frontière de l'empilement. Selon le théorème d'empilement de cercles, ce graphe planaire peut être représenté par un empilement de cercles C dans lequel toutes les arêtes (y compris celles incidentes au sommet de la frontière) sont représentées par des tangences de cercles. Les cercles de l'empilement de A correspondent un à un aux cercles de C, à l'exception du cercle de la frontière de C qui correspond à la frontière de A. Cette correspondance des cercles peut être utilisée pour construire une fonction continue de A à C dans laquelle chaque cercle et chaque espace entre trois cercles est envoyé d'un empilement à l'autre par une transformation de Möbius. Thurston a conjecturé que, dans la limite où le rayon r tend vers zéro, les fonctions de A à C construites de cette manière se rapprocheraient de la transformation conforme donnée par le théorème de Riemann^[2].

La conjecture de Thurston a été prouvée en 1987 par Rodin et Sullivan^[3]. Plus précisément, ils ont montré que, lorsque n tend vers l'infini, la fonction f_n déterminée en utilisant la méthode de Thurston à partir des empilements hexagonaux de cercles de rayon 1/n converge uniformément sur les sous-ensembles compacts de A vers une transformation conforme de A vers C^[2].

Malgré le succès de la conjecture de Thurston, les applications pratiques de cette méthode ont été freinées par la difficulté de calculer les empilements de cercles et par son taux de convergence relativement lent^[4]. Cependant, elle présente certains avantages lorsqu'elle est appliquée à des domaines non simplement connexes et dans le choix des approximations initiales pour les techniques numériques qui calculent les applications de Schwartz-Christoffel (en), une technique différente de détermination de transformations conformes entre domaines polygonaux^[2].

Il existe de nombreuses démonstrations du théorème d'empilement de cercles. La preuve originale de Paul Koebe est basée sur son théorème d'uniformisation conforme disant qu'un ouvert planaire ayant un nombre fini de composantes connexes est conforme à un ensemble de disques. Plusieurs preuves topologiques différentes sont également connues. La preuve de Thurston est basée sur le théorème du point fixe de Brouwer. En tant qu'étudiant diplômé, Oded Schramm a été supervisé par Thurston à l'Université de Princeton. Comme le raconte Rohde 2011, p. 1628, il y a une "description poétique" dans la thèse de Schramm sur la manière dont l'existence d'un empilement de cercles peut être déduite du théorème du point fixe : « On peut juste voir le terrible monstre agiter ses bras dans une rage pure, les tentacules provoquant un sifflement effrayant, en se frottant les uns contre les autres ». Il existe également une preuve utilisant une variante discrète de la méthode de Perron (en) pour construire des solutions au problème de Dirichlet^[5]. Yves Colin de Verdière a prouvé l'existence de l'empilement de cercles comme minimisant une fonction convexe sur un certain espace de configurations^[6].

Le théorème d'empilement de cercles est un outil utile pour étudier divers problèmes de géométrie planaire, de transformations conformes et de graphes planaires. Une autre preuve du théorème du séparateur planaire, initialement due à Lipton et Tarjan^[7], a été obtenue de cette manière^[8]. Une autre application du théorème d'empilement de cercles est que les limites non biaisées des graphes planaires de degré borné sont presque sûrement récurrentes^[9]. D'autres applications incluent des estimations de la plus grande valeur propre des graphes de genre borné^[10].

En tracé de graphes, l'empilement de cercles a été utilisé pour trouver des tracés de graphes planaires ayant une résolution angulaire (en) bornée^[11] et avec un nombre de pente (en) borné^[12]. Le théorème de Fáry (en), selon lequel chaque graphe qui peut être dessiné sans croisements dans le plan en utilisant des arêtes courbes peut également être dessiné sans croisements en n'utilisant que des segments de droite, découle comme un simple corollaire du théorème d'empilement de cercles : en plaçant les sommets aux centres des cercles et en dessinant des arêtes droites entre eux, un plongement planaire en ligne droite est obtenu.

Une forme plus forte du théorème d'empilement de cercles affirme que tout graphe polyédrique et son graphe dual peuvent être représentés par deux empilements de cercles, de sorte que les deux cercles tangents représentant une arête du graphe primal et les deux cercles tangents représentant le dual de la même arête aient toujours leurs tangences à angle droit l'un par rapport à l'autre au même point du plan. Un empilement de ce type peut être utilisé pour construire un polyèdre convexe représentant le graphe donné et ayant une sphère médiane, tangente à toutes les arêtes du polyèdre. Inversement, si un polyèdre a une sphère médiane, alors les cercles formés par les intersections de la sphère avec les faces du polyèdre et les cercles formés par les horizons sur la sphère vus de chaque sommet du polyèdre (les cercles de tangence des cônes issus de ces sommets) forment deux empilements duaux de ce type.

Collins et Stephenson 2003 décrivent un algorithme de relaxation (en) numérique pour trouver des empilements de cercles, basé sur les idées de William Thurston. La version du problème d'empilement de cercles qu'ils résolvent prend en entrée un graphe planaire, dans lequel toutes les faces internes sont des triangles et pour lequel les sommets externes ont été étiquetés par des nombres positifs. Il produit en sortie un empilement de cercles dont les tangences représentent le graphe donné, et pour lequel les cercles représentant les sommets externes ont les rayons spécifiés dans l'entrée. Comme ils le suggèrent, la clé du problème est d'abord de calculer les rayons des cercles dans l'empilement ; une fois les rayons connus, les positions géométriques des cercles ne sont pas difficiles à calculer. Ils commencent avec un ensemble de rayons provisoires qui ne correspondent pas à un empilement valide, puis effectuent à plusieurs reprises les étapes suivantes :

1. Choisir un sommet interne v du graphe d'entrée.
2. Calculer l'angle total θ que ses k cercles voisins couvriraient autour du cercle pour v, si les voisins étaient placés tangents les uns aux autres et au cercle central en utilisant leurs rayons provisoires.
3. Déterminer un rayon représentatif r pour les cercles voisins, de sorte que k cercles de rayon r donnent le même angle de couverture θ que les voisins de v donnent.
4. Définir le nouveau rayon pour v comme la valeur pour laquelle k cercles de rayon r donneraient un angle de couverture exactement égal à 2π.

Chacune de ces étapes peut être effectuée avec des calculs trigonométriques simples, et comme l'affirment Collins et Stephenson, le système de rayons converge rapidement vers un point fixe unique pour lequel tous les angles de couverture sont exactement de 2π. Une fois que le système a convergé, les cercles peuvent être placés un à un, en utilisant à chaque étape les positions et les rayons de deux cercles voisins pour déterminer le centre de chaque cercle successif.

Mohar 1993 décrit une technique itérative similaire pour trouver des empilements simultanés d'un graphe polyédrique et de son dual, dans lesquels les cercles du dual sont à angle droit par rapport aux cercles du primal. Il prouve que la méthode prend un temps polynomial dans le nombre de cercles et dans log 1/ε, où ε est une limite sur la distance des centres et des rayons de l'empilement calculé par rapport à ceux d'un empilement optimal.

Le théorème d'empilement de cercles se généralise aux graphes non planaires. Si G est un graphe qui peut être plongé sur une surface S, alors il existe une courbure métrique riemannienne d sur S et un empilement de cercles sur (S, d) dont le graphe de contacts est isomorphe à G. Si S est fermée (compacte et sans bord) et G est une triangulation de S, alors (S, d) et l'empilement sont uniques à une équivalence conforme près. Si S est la sphère, alors cette équivalence est à transformations de Möbius près ; si c'est un tore, alors l'équivalence est à homothétie près et à isométries près, tandis que si S a un genre d'au moins 2, alors l'équivalence est à isométries près.

Une autre généralisation du théorème d'empilement de cercles implique de remplacer la condition de tangence par un angle d'intersection spécifié entre les cercles correspondant aux sommets voisins. Une version particulièrement élégante est la suivante. Supposons que G soit un graphe planaire 3-connexe (en) fini (c'est-à-dire un graphe polyédrique), alors il existe une paire d'empilements de cercles, l'un dont le graphe d'intersection est isomorphe à G, l'autre dont le graphe d'intersection est isomorphe au dual planaire de G, et pour chaque sommet de G et face adjacente à celui-ci, le cercle dans le premier empilement correspondant au sommet intersecte orthogonalement le cercle dans le second empilement correspondant à la face^[13]. Par exemple, en appliquant ce résultat au graphe du tétraèdre, on obtient, pour quatre cercles mutuellement tangents, un deuxième ensemble de quatre cercles mutuellement tangents, chacun étant orthogonal à trois des quatre premiers^[14]. Une autre généralisation, remplaçant l'angle d'intersection par la distance inversive (en), permet de spécifier des empilements dans lesquels certains cercles doivent être disjoints les uns des autres plutôt que de se croiser ou d'être tangents^[15].

Encore une autre sorte de généralisation s'intéresse à des formes qui ne sont pas des cercles. Supposons que G = (V, E) soit un graphe planaire fini, et qu'à chaque sommet v de G corresponde une forme ${\displaystyle K_{v}\subset \mathbb {R} ^{2}}$, qui est homéomorphe au disque unité fermé et dont la frontière est lisse. Alors il existe un empilement ${\displaystyle P=(K'_{v}:v\in V)}$ dans le plan tel que ${\displaystyle K'_{v}\cap K'_{u}\neq \varnothing }$ si et seulement si ${\displaystyle [v,u]\in E}$ et pour chaque ${\displaystyle v\in V}$, l'ensemble ${\displaystyle K'_{v}}$ est obtenu à partir de ${\displaystyle K_{v}}$ par translation et homothétie. (Notez que dans le théorème original d'empilement de cercles, il y a trois paramètres réels par sommet, dont deux décrivent le centre du cercle correspondant et un décrit le rayon, et il y a une équation par arête. Cela vaut aussi dans cette généralisation.) Une preuve de cette généralisation peut être obtenue en appliquant la preuve originale de Koebe^[16] et le théorème de Brandt^[17] et Harrington^[18] stipulant que tout domaine de connexité finie est conforme à un domaine planaire dont les composantes de la frontière ont des formes spécifiées, à translations et homothéties près.

Les empilements de cercles ont été étudiés dès 1910, dans les travaux d'Arnold Emch (en) sur les spirales de Doyle (en) en phyllotaxie (les mathématiques de la croissance des plantes)^[19]. Le théorème d'empilement de cercles a été démontré pour la première fois par Paul Koebe^[16]. William Thurston^[1] a redécouvert le théorème, et a noté qu'il découlait des travaux d'E. M. Andreev. Thurston a également proposé un schéma pour utiliser le théorème d'empilement de cercles pour obtenir un homéomorphisme d'un sous-ensemble simplement connexe du plan à l'intérieur du disque unité. La conjecture de Thurston pour les empilements de cercles est sa conjecture selon laquelle l'homéomorphisme convergera vers l'application conforme garantie par le théorème de Riemann lorsque les rayons des cercles tendent vers zéro. La conjecture de Thurston a été démontrée ensuite par Burton Rodin (en) et Dennis Sullivan^[3]. Cela a conduit à de nombreuses recherches sur les extensions du théorème d'empilement de cercles et ses relations avec les transformations conformes.

• Baderne d'Apollonius
• Empilement de cercles
• Cercle de Ford

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Circle packing theorem » (voir la liste des auteurs).
• (en) E. M. Andreev, « Convex polyhedra in Lobačevskiĭ spaces », Mat. Sb., vol. 81, n^o 123,‎ 1970, p. 445–478 (DOI 10.1070/SM1970v010n03ABEH001677, Bibcode 1970SbMat..10..413A, MR 0259734).
• (en) Alan F. Beardon et Kenneth Stephenson, « The uniformization theorem for circle packings », Indiana Univ. Math. J., vol. 39, n^o 4,‎ 1990, p. 1383–1425 (DOI 10.1512/iumj.1990.39.39062 , lire en ligne)
• (en) Alan F. Beardon et Kenneth Stephenson, « The Schwarz-Pick lemma for circle packings », Illinois J. Math., vol. 35, n^o 4,‎ 1991, p. 577–606 (DOI 10.1215/ijm/1255987673 , lire en ligne)
• (en) E. M. Andreev, « Convex polyhedra of finite volume in Lobačevskiĭ space », Mat. Sb., vol. 83, n^o 125,‎ 1970, p. 256–260 (DOI 10.1070/SM1970v012n02ABEH000920, Bibcode 1970SbMat..12..255A, MR 0273510).
• (en) Itai Benjamini et Oded Schramm, « Recurrence of distributional limits of finite planar graphs », Electronic Journal of Probability, vol. 6,‎ 2001 (DOI 10.1214/EJP.v6-96 , MR 1873300, S2CID 2862151, lire en ligne).
• (de) M. Brandt, « Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete », Bull. De la Soc. Des Sc. Et des Lettr. De Łódź, vol. 30,‎ 1980.
• (en) Graham R. Brightwell et Edward R. Scheinerman, « Representations of planar graphs », SIAM J. Discrete Math., vol. 6, n^o 2,‎ 1993, p. 214–229 (DOI 10.1137/0406017).
• (en) Ithiel Carter et Burt Rodin, « An inverse problem for circle packing and conformal mapping », Transactions of the American Mathematical Society, vol. 334, n^o 2,‎ 1992, p. 861–875 (DOI 10.1090/S0002-9947-1992-1081937-X , lire en ligne)
• Yves Colin de Verdière, « Un principe variationnel pour les empilements de cercles », Inventiones Mathematicae, vol. 104, n^o 1,‎ 1991, p. 655–669 (DOI 10.1007/BF01245096, Bibcode 1991InMat.104..655C, S2CID 121028882).
• (en) Charles R. Collins et Kenneth Stephenson, « A circle packing algorithm », Computational Geometry. Theory and Applications, vol. 25, n^o 3,‎ 2003, p. 233–256 (DOI 10.1016/S0925-7721(02)00099-8 , MR 1975216).
• (en) Andrew N. Harrington, « Conformal mappings onto domains with arbitrarily specified boundary shapes », Journal d'Analyse Mathématique (en), vol. 41, n^o 1,‎ 1982, p. 39–53 (DOI 10.1007/BF02803393 , S2CID 120752035)
• (en) Johan Jonnason et Oded Schramm, « On the cover time of planar graphs », Electronic Communications in Probability, vol. 5,‎ 2000, p. 85–90 (lire en ligne).
• (en) Jonathan A. Kelner, « Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus », SIAM Journal on Computing, vol. 35, n^o 4,‎ 2006, p. 882–902 (DOI 10.1137/S0097539705447244, hdl 1721.1/30169 ).
• (en) Balázs Keszegh, János Pach et Dömötör Pálvölgyi, « Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers », Lecture Notes in Computer Science, Heidelberg, Springer, vol. 6502,‎ 2011, p. 293–304 (DOI 10.1007/978-3-642-18469-7_27, MR 2781274, arXiv 1009.1315, S2CID 817874).
• (de) Paul Koebe, « Kontaktprobleme der Konformen Abbildung », Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., vol. 88,‎ 1936, p. 141–164.
• (en) Richard J. Lipton et Robert E. Tarjan, « A separator theorem for planar graphs », SIAM Journal on Applied Mathematics, vol. 36, n^o 2,‎ 1979, p. 177–189 (DOI 10.1137/0136016, CiteSeer^x 10.1.1.104.6528).
• (en) Seth Malitz et Achilleas Papakostas, « On the angular resolution of planar graphs », SIAM Journal on Discrete Mathematics, vol. 7, n^o 2,‎ 1994, p. 172–183 (DOI 10.1137/S0895480193242931, MR 1271989).
• (en) Gary L. Miller, Shang-Hua Teng, William Thurston et Stephen A. Vavasis, « Separators for sphere-packings and nearest neighbor graphs », J. ACM, vol. 44, n^o 1,‎ 1997, p. 1–29 (DOI 10.1145/256292.256294 , S2CID 17331739).
• (en) Bojan Mohar, « A polynomial time circle packing algorithm », Discrete Mathematics, vol. 117, n^os 1–3,‎ 1993, p. 257–263 (DOI 10.1016/0012-365X(93)90340-Y ).
• (en) Burton Rodin et Dennis Sullivan, « The convergence of circle packings to the Riemann mapping », Journal of Differential Geometry, vol. 26, n^o 2,‎ 1987, p. 349–360 (DOI 10.4310/jdg/1214441375 , lire en ligne).
• (en) Steffen Rohde, « Oded Schramm: from circle packing to SLE », Ann. Probab., vol. 39, n^o 5,‎ 2011, p. 1621–1667 (DOI 10.1214/10-AOP590 , arXiv 1007.2007, lire en ligne)
• (en) Kenneth Stephenson, Computational methods and function theory 1997 (Nicosia), vol. 11, World Sci. Publ., River Edge, NJ, coll. « Ser. Approx. Decompos. », 1999, 551–582 p. (MR 1700374).
• (en) Kenneth Stephenson, « Circle packing: a mathematical tale », Notices Amer. Math. Soc., vol. 50,‎ 2003, p. 1376–1388 (lire en ligne)
• (en) Kenneth Stephenson, Introduction to circle packing, the theory of discrete analytic functions, Cambridge, Cambridge University Press, 2005.
• (en) William Thurston, The finite Riemann mapping theorem, coll. « Invited talk at the International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture », 1985.
• (en) William Thurston, The geometry and topology of 3-manifolds, Princeton lecture notes, 1978–1981 (lire en ligne).

• CirclePack (logiciel libre pour construire des empilements de cercles à partir de graphes)
• (en)Bibliographie sur les empilements de cercles par Kenneth Stephenson, Université du Tennessee

• Portail de la géométrie