Teorema de ambalare a cercurilor

Teorema de împachetare a cercurilor (cunoscută și ca teorema Koebe-Andreev-Thurston ) descrie modul în care cercurile pot fi atinse dacă nu au puncte interioare comune. Un grafic de intersecție (uneori numit grafic de tangență ) al unui pachet de cercuri este un grafic ale cărui vârfuri corespund unor cercuri și ale cărui muchii corespund punctelor de tangență. Dacă cercurile sunt împachetate pe un plan (sau, în mod echivalent, pe o sferă), atunci graficul lor de intersecție se numește grafic monedă . Graficele de monede sunt întotdeauna conectate, simple și plane . Teorema de împachetare a cercurilor afirmă că și inversul este adevărat:

Teorema de împachetare a cercului : Pentru orice graf planar simplu conectat G , există un cerc de împachetare în plan al cărui grafic de intersecție este izomorf cu G.

Unicitate

Un grafic G se numește plan triangulat (sau plan maxim) dacă este plan și orice componentă conexă a complementului înglobării lui G într-o sferă are exact trei muchii la graniță sau, cu alte cuvinte, dacă G este una. -arborele de acoperire dimensional al unui complex simplist care este homeomorf unei sfere. Orice graf planar triangulat G este conex și simplu, deci teorema de împachetare a cercurilor garantează existența unui graf al cărui graf de tangență este izomorf cu G . Un astfel de grafic G trebuie să fie finit, astfel încât împachetarea corespunzătoare va avea un număr finit de cercuri. După cum arată următoarea teoremă, orice graf planar maximal poate corespunde la cel mult un pachet.

Teorema Koebe–Andreev–Thurston : Dacă G este un grafic planar triangulat finit, atunci un cerc al cărui grafic de tangență este (izomorf cu) G este unic până la transformările și reflexiile Möbius în raport cu liniile.

Thurston [1] a observat că această unicitate este o consecință a teoremei de rigiditate a lui Mostow . Planul în care sunt împachetate cercurile poate fi văzut ca limită a modelului Poincaré într-un semi-spațiu . Din acest punct de vedere, orice cerc este limita unui plan în spațiul hiperbolic. Fiecare împachetare de cercuri poate fi asociată cu un set de planuri care nu se intersectează, precum și cu un al doilea set de planuri care nu se intersectează definite prin zone triunghiulare dintre cele trei cercuri de împachetare. Planele din diferite mulțimi se intersectează în unghi drept și corespund generatoarelor grupului de reflexie , al cărui domeniu fundamental poate fi considerat ca o varietate hiperbolică . Prin teorema de rigiditate a lui Mostow, structura hiperbolică a acestui domeniu este definită în mod unic până la izometriile spațiului hiperbolic. Aceste izometrii, atunci când sunt considerate în termeni de acțiune la granița modelului Poincaré, se transformă în transformări Möbius.

Există și o dovadă elementară bazată pe principiul maximului și pe observația că într-un triunghi care leagă centrele a trei cercuri reciproc tangente, unghiul format la vârful din centrul unuia dintre cercuri scade monoton pe măsură ce raza lui crește și crește. monoton pe măsură ce oricare dintre celelalte două cercuri crește.razele. Având în vedere două împachetari pentru același grafic G , reflexiile și transformările Möbius pot fi utilizate pentru a face ca cercurile exterioare din cele două împachetari să corespundă între ele și să aibă aceleași raze. Apoi, fie v  un vârf interior al lui G pentru care cercurile în două pachete au dimensiuni cât mai îndepărtate. Adică, v este ales pentru a maximiza raportul r 1 / r 2 al razelor cercurilor celor două pachete. Rezultă că pentru fiecare față triunghiulară a lui G care conține v , unghiul cu vârful centrului cercului corespunzător lui v din prima împachetare este mai mic sau egal cu unghiul din a doua împachetare, cu egalitate numai dacă celelalte două cercurile formează un triunghi cu același raport r 1 / r 2 razele celei de-a doua garnituri. Dar suma unghiurilor tuturor triunghiurilor care înconjoară centrul triunghiului trebuie să fie 2π în ambele pachete, astfel încât toate vârfurile adiacente v trebuie să aibă același raport cu cel al lui v însuși . Aplicând același raționament altor cercuri, se dovedește că toate cercurile din ambele pachete au aceeași relație. Dar cercurile exterioare sunt transformate pentru a avea un raport de 1, astfel încât r 1 / r 2 = 1 și ambele pachete au raze egale pentru toate cercurile.

Generalizări ale teoremei de împachetare în cerc

Împachetarea cercurilor poate fi generalizată la grafice care nu sunt plane.

Dacă G este un grafic care poate fi încorporat într-o suprafață orientabilă S , atunci există o metrică riemanniană d de curbură constantă pe S și un cerc înglobat în ( S , d ) al cărui grafic de tangență este izomorf cu G. Dacă S este închis ( compact și nu are graniță ) și G  este o triangulație a lui S , atunci ( S , d ) și ambalarea sunt unice până la echivalența conformă. Dacă S  este o sferă, atunci o echivalență conformă este o echivalență până la transformările Möbius; dacă este un tor, atunci până la înmulțirea cu o constantă și izometrii; dacă genul suprafeței este de cel puțin 2, până la izometrie.

O altă generalizare a teoremei de împachetare a cercurilor implică înlocuirea condiției de tangență prin specificarea unghiului de intersecție între cercurile corespunzătoare vârfurilor învecinate. În special, există următoarea versiune elegantă a acestei teoreme. Să presupunem că G este un grafic planar finit cu 3 conexiuni (cu alte cuvinte, un grafic poliedric ), atunci există o pereche de pachete de cerc, astfel încât graficul de intersecție al unui pachet este izomorf cu G , iar graficul de intersecție al celuilalt este izomorf. la graficul dual planar al lui G. Mai mult, pentru orice vârf din G și o față adiacentă acestuia, cercul corespunzător vârfului din prima împachetare se intersectează în unghi drept cu cercul corespunzător feței din a doua împachetare [2] . De exemplu, aplicarea acestui rezultat la un grafic al unui tetraedru dă, pentru oricare patru cercuri tangente pe perechi, un al doilea set de patru cercuri reciproc tangente, fiecare dintre acestea fiind ortogonal la trei din primul set [3] . O generalizare suplimentară poate fi obținută prin înlocuirea unghiului de intersecție cu o distanță inversă [4] .

O altă generalizare permite utilizarea altor forme decât cercurile. Să presupunem că G = ( V , E ) este un grafic plan finit și fiecare vârf v al lui G corespunde unei figuri care este homeomorfă discului unitar închis și a cărei graniță este netedă. Apoi există o împachetare în plan astfel încât dacă și numai dacă și pentru fiecare setul este obținut prin deplasare și scalare. (Rețineți că teorema originală de împachetare a cercurilor are trei parametri de vârf, dintre care doi specifică centrul cercului corespunzător și unul specifică raza și există o ecuație pentru fiecare muchie. Acest lucru este valabil și pentru această generalizare.) O dovadă a această generalizare este obținută prin utilizarea dovezii originale a lui Koebe [5] și a teoremei lui Brandt [6] și Harrington [7] care afirmă că orice domeniu conex finit este echivalent conform unui domeniu plat ale cărui granițe componente au forme specifice până la translație și scalare.

Relația cu teoria mapărilor conformale

O mapare conformă între două subseturi deschise ale unui plan sau spațiu de dimensiuni mai mari este continuă și păstrează unghiurile dintre oricare două curbe. Teorema de mapare Riemann , formulată de Riemann în 1851, afirmă că pentru oricare două discuri topologice deschise din plan, există o mapare conformă de la un disc la altul.

Mapările conforme au aplicații în construcția de grile de calcul , proiecții de hărți și alte domenii. Cu toate acestea, nu este întotdeauna ușor să construiți o mapare conformă între două regiuni date în mod explicit [8] .

La o conferință din 1985, William Thurston a sugerat că împachetarea cercurilor ar putea fi folosită pentru a aproxima mapările conforme. Mai precis, Thurston a folosit împachetarea cercurilor pentru a găsi o mapare conformă a unui disc A arbitrar deschis (topologic) în interiorul unui cerc. O mapare de la un disc topologic la un alt disc B poate fi apoi găsită prin suprapunerea unei mapări de la A la un cerc și o mapare inversă mapării lui B la un cerc [9] .

Ideea lui Thurston a fost să construiască un pachet de cercuri cu o rază mică r sub forma unei plăci hexagonale [10] pe planul din interiorul regiunii A , lăsând o fâșie îngustă lângă limita lui A , în care încă un cerc de această rază. nu poate fi plasat. Apoi , graficul planar maxim G este construit din graficul de intersecție a cercului și se adaugă un vârf suplimentar adiacent tuturor cercurilor de pe limita de împachetare. Prin teorema cercurilor, acest grafic plan poate fi reprezentat printr-un cerc C în care toate muchiile (inclusiv muchiile incidente la vârfurile limită) sunt reprezentate prin tangența cercurilor. Cercurile din ambalajul A corespund unu la unu cercurilor din C , cu excepția cercului de limită C , care corespunde limitei lui A . Această corespondență poate fi folosită pentru a construi o mapare continuă de la A la C , în care fiecare cerc și fiecare decalaj dintre trei cercuri este mapat de la un pachet la altul folosind o transformare Möbius . Thurston a sugerat că, pe măsură ce raza r tinde spre zero, maparea de la A la C , construită în acest fel, tinde către o funcție conformă, care este dată de teorema lui Riemann [9] .

Conjectura lui Thurston a fost dovedită de Rodin și Sullivan [11] . Mai precis, ei au arătat că pe măsură ce n tinde spre infinit, funcția f n obținută prin metoda lui Thurston converge uniform pe submulțimile compacte A de la o împachetare cu cercuri de rază 1/ n la o mapare conformă de la A la C [9] .

În ciuda confirmării conjecturii lui Thurston, aplicarea practică a acestei metode este îngreunată de complexitatea construirii împachetărilor circulare și de convergența relativ lentă. Totuși, această metodă poate fi utilizată cu succes în cazul domeniilor neconectate pur și simplu și în alegerea aproximărilor inițiale pentru metodele numerice care calculează mapările Schwartz-Christoffel  - o metodă oarecum diferită pentru construirea mapărilor conformale ale domeniilor poligonale [9] .

Aplicații ale teoremei de împachetare în cerc

Teorema de împachetare a cercurilor este un instrument util pentru studierea diferitelor probleme în planimetrie, mapări conforme și grafice plane. O demonstrație elegantă a teoremei de partiționare a grafului plan , demonstrată inițial de Lipton și Tarjan [12] , este obținută folosind teorema de împachetare a cercurilor [13] . O altă aplicație a teoremei de împachetare a cercurilor este de a demonstra afirmația că limitele nepărtinitoare ale grafurilor plane cu grad mărginit sunt aproape întotdeauna recursive [14] .

Alte aplicații sunt derivațiile pentru timpul de parcurgere aleatorie a unui grafic [15] și estimarea valorii proprii maxime a graficelor de gen mărginit [16] .

În vizualizarea graficului, împachetarea cercurilor este utilizată pentru a găsi o reprezentare a unui grafic plan cu rezoluție limitată [17] și cu un număr limitat de pante [18] .

Demonstrarea teoremei

Există multe dovezi binecunoscute ale teoremei de ambalare a cercurilor. Dovada originală a lui Paul Koebe se bazează pe teorema sa de parametrizare conformă care afirmă că un domeniu finit conectat este echivalent conform unui cerc. Există mai multe dovezi topologice cunoscute. Dovada lui Thurston se bazează pe teorema punctului fix a lui Brouwer .

Există, de asemenea, o demonstrație folosind o versiune discretă a metodei Perron pentru construirea unei soluții la problema Dirichlet . Yves Colin de Verdière a demonstrat [19] existența unei împachetari cercului ca minimizator al unei funcții convexe pe unele spații de configurare.

Consecințele

Teorema lui Faree , care afirmă că orice grafic care poate fi reprezentat fără intersecții în plan folosind muchii curbe, poate fi desenat și fără intersecții folosind segmente de linie, este o consecință simplă a teoremei de împachetare a cercurilor - plasarea vârfurilor în centrele cercurilor. și desenând segmente de linie care leagă cercurile care se ating, obținem o reprezentare cu margini sub formă de segmente.

O versiune strictă a teoremei de împachetare afirmă că orice graf poliedric și graficul său dual pot fi reprezentate prin două pachete de cercuri, astfel încât cele două cercuri tangente reprezentând o margine a graficului de bază și celelalte două cercuri tangente reprezentând o margine a grafului dual. graficul se intersectează în unghi drept. Acest tip de împachetare poate fi folosit pentru a construi un poliedru convex care este reprezentat printr-un grafic dat și are o sferă semi-înscrisă , o sferă tangentă la toate muchiile poliedrului . În schimb, dacă un poliedru are o sferă semiînscrisă, atunci se formează cercurile formate prin intersecția sferei cu fețele poliedrului și cercurile formate din orizonturile sferei, care sunt vizibile de la vârfurile poliedrului. ambalaje duble.

Aspecte algoritmice

Collins și Stephenson [20] au descris un algoritm de relaxare numerică pentru găsirea împachetarii cercurilor bazate pe ideile lui William Thurston . Versiunea problemei cercurilor pe care o rezolvă ia ca intrare un grafic plan în care toate fețele interioare sunt triunghiuri și toate vârfurile exterioare sunt etichetate cu numere pozitive. Algoritmul produce un pachet de cercuri ale căror puncte tangente reprezintă graficul dat și pentru care cercurile reprezentând vârfurile exterioare au raza dată în intrare. După cum au sugerat, cheia problemei constă în calculul inițial al razelor cercurilor de împachetare. Dacă razele sunt cunoscute, pozițiile geometrice ale cercurilor nu sunt greu de calculat. Încep cu raze de încercare care nu se potrivesc cu pachetele reale, apoi parcurg următorii pași:

  1. Să alegem un vârf intern al graficului de intrare, acest vârf corespunde unui cerc, pe care îl vom nota v . Vârfurile învecinate corespund lobilor , adică cercuri tangente la cercul selectat. Fie k  numărul de petale.
  2. Calculați unghiul total θ care este suprapus de k cercuri învecinate în jurul cercului v , dacă sunt plasate unul lângă celălalt și care ating cercul central.
  3. Calculați raza medie r s pentru petalele astfel încât k cercuri cu raza r s să se suprapună cu același unghi θ dat de vecinii v .
  4. Setați o nouă rază r n pentru v astfel încât k cercuri de rază medie să se suprapună exact 2π.

Fiecare dintre acești pași poate fi făcut cu calcule trigonometrice simple și, după cum au subliniat Collins și Stephenson, sistemul de raze converge către un singur punct fix pentru care toate unghiurile de acoperire sunt 2π. Odată ce sistemul de raze a convergit, cercurile pot fi plasate pe rând, la fiecare pas folosind poziția și razele celor două cercuri adiacente pentru a calcula centrul fiecărui cerc reușit.

Mohar [21] descrie o tehnică iterativă similară pentru găsirea împachetărilor unui graf poliedric și a dualului său în care ciclurile duale se intersectează în unghi drept cu cercurile subiacente. El a demonstrat că metoda funcționează în timp polinomial în numărul de cercuri și în log 1/ε, unde ε este limita distanțelor de la centre și diferența dintre razele împachetării calculate și împachetarea optimă.

Istorie

Teorema de împachetare a cercurilor a fost demonstrată pentru prima dată de Paul Koebe [5] .

William Thurston [1] a redescoperit teorema de împachetare a cercurilor și a observat că aceasta rezultă din lucrarea lui E. M. Andreev. Thurston a propus, de asemenea, o schemă de utilizare a teoremei de împachetare a cercului pentru a obține un homeomorfism al unei mulțimi conectate în planul la interiorul cercului unitar. Conjectura cercurilor lui Thurston  este presupunerea că un homeomorfism converge către o hartă Riemann pe măsură ce razele tind spre zero. Conjectura lui Thurston a fost demonstrată ulterior de Burton Rodin și Dennis Sullivan [11] . Acest lucru a condus la numeroase studii privind generalizările teoremei de împachetare în cerc, precum și studii privind relațiile cu mapările conforme și aplicațiile teoremei.

Vezi și

Note

  1. ↑ 1 2 Thurston, 1978-1981 .
  2. ↑ Brightwell, Scheinerman, 1993 , p. 214-229.
  3. ↑ Coxeter, 2006 , p. 109-114.
  4. ↑ Bowers, Stephenson, 2004 , p. 78-82.
  5. ↑ 1 2 Koebe, 1936 , p. 141-164.
  6. ↑ Brandt, 1980 .
  7. ↑ Harrington, 1982 , p. 39-53.
  8. ↑ Stephenson, 1999 , p. 551-582.
  9. ↑ 1 2 3 4 Stephenson, 1999 .
  10. ↑ Dacă centrele cercurilor formează o rețea dreptunghiulară, împachetarea se numește pătrat. Dacă centrele cercurilor formează o rețea triunghiulară, împachetarea se numește hexagonală.
  11. ↑ 1 2 Rodin și Sullivan 1987 , p. 349-360.
  12. ↑ Lipton, Tarjan, 1979 .
  13. ↑ Miller, Teng, Thurston, Vavasis, 1997 , p. 1-29.
  14. ↑ Benjamini, Schramm, 2001 .
  15. ↑ Jonnason, Schramm, 2000 .
  16. ↑ Kelner, 2006 , p. 882-902.
  17. ↑ Malitz și Papakostas 1994 , p. 172-183.
  18. ↑ Keszegh, Pach, Pálvölgyi, 2011 , p. 293-304.
  19. ↑ Verdière, 1991 , p. 655-669.
  20. ↑ Collins, Stephenson, 2003 , p. 233-256.
  21. ↑ Mohar, 1993 , p. 257-263.

Literatură

Link -uri

 Sarcini de ambalare
Cercuri de ambalare
Ambalare cu baloane
Alte pachete
Puzzle