Věta o balení kruhu

Věta o balení kružnic (také známá jako Koebe-Andreev-Thurstonova věta ) popisuje, jak se lze dotknout kruhů, pokud nemají žádné společné vnitřní body. Průsečíkový graf (někdy nazývaný graf tečnosti ) skupiny kružnic je graf , jehož vrcholy odpovídají kružnicím a jejichž hrany odpovídají bodům tečnosti. Jsou-li kružnice seskupeny na rovině (nebo ekvivalentně na kouli), pak se jejich graf průsečíku nazývá graf mincí . Mincové grafy jsou vždy spojené, jednoduché a rovinné . Věta o balení kruhu říká, že opak je také pravdivý:

Věta o kružnici : Pro každý souvislý jednoduchý rovinný graf G existuje kružnice v rovině, jejíž průsečík je izomorfní s G.

Jedinečnost

Graf G se nazývá triangulovaný rovinný (nebo maximální rovinný), pokud je rovinný a jakákoliv souvislá složka doplňku vnoření G do koule má na hranici právě tři hrany, nebo, jinými slovy, je-li G jedna. -dimenzionální kostra jednoduchého komplexu , který je homeomorfní ke kouli. Libovolný triangulovaný rovinný graf G je souvislý a jednoduchý, takže teorém o balení kruhu zaručuje existenci balení, jehož graf tečnosti je izomorfní k G . Takový graf G musí být konečný, takže odpovídající balení bude mít konečný počet kružnic. Jak uvádí následující věta, každý maximální rovinný graf může odpovídat nejvýše jednomu balení.

Koebeova–Andreevova–Thurstonova věta : Je-li G konečný triangulovaný rovinný graf, pak kružnice, jejíž graf tečnosti je (izomorfní) G , je jedinečný až do Möbiových transformací a odrazů s ohledem na přímky.

Thurston [1] poznamenal, že tato jedinečnost je důsledkem Mostowova teorému tuhosti . Rovina, ve které jsou kruhy zabaleny, může být viděna jako hranice Poincarého modelu v poloprostoru . Z tohoto pohledu je jakákoli kružnice hranicí roviny v hyperbolickém prostoru. Každé uspořádání kruhů může být spojeno se sadou neprotínajících se rovin, stejně jako s druhou sadou neprotínajících se rovin definovaných trojúhelníkovými oblastmi mezi třemi balicími kruhy. Roviny z různých množin se protínají v pravých úhlech a odpovídají generátorům odrazové grupy , jejíž základní doménu lze považovat za hyperbolickou varietu . Podle Mostowova teorému tuhosti je hyperbolická struktura této domény jednoznačně definována až do izometrií hyperbolického prostoru. Tyto izometrie, když je uvažujeme z hlediska působení na hranici Poincarého modelu, se promění v Möbiovy transformace.

Existuje také elementární důkaz založený na principu maxima a na pozorování, že v trojúhelníku spojujícím středy tří vzájemně tečných kružnic se úhel sevřený ve vrcholu ve středu jedné z kružnic monotónně zmenšuje se zvětšováním a zvětšováním jeho poloměru. monotónně, jak se kterýkoli z dalších dvou kruhů zvětšuje. Daná dvě balení pro stejný graf G , odrazy a Möbiovy transformace mohou být použity k tomu, aby si vnější kružnice ve dvou baleních navzájem odpovídaly a měly stejné poloměry. Potom nechť v  je vnitřní vrchol G , pro který mají kruhy složené ve dvou velikostech co nejdále od sebe. To znamená, že v je zvoleno tak , aby maximalizovalo poměr r1 / r2 poloměrů kružnic dvou balíčků . Z toho vyplývá, že pro každou trojúhelníkovou plochu G obsahující v je úhel s vrcholem středu kružnice odpovídající v v prvním obalu menší nebo roven úhlu ve druhém obalu, přičemž je rovnost pouze v případě, že ostatní dva kruhy tvoří trojúhelník se stejným poměrem poloměrů r 1 / r 2 druhého obalu. Ale součet úhlů všech trojúhelníků obklopujících střed trojúhelníku musí být v obou obalech 2π, takže všechny vrcholy sousedící s v musí mít stejný poměr jako v samotném . Aplikujeme-li stejnou úvahu na další kruhy, ukázalo se, že všechny kruhy v obou balíčcích mají stejný vztah. Ale vnější kruhy jsou transformovány tak, aby měly poměr 1, takže r 1 / r 2 = 1 a oba balíčky mají stejné poloměry pro všechny kruhy.

Zobecnění teorému o balení kruhu

Kruhové balení lze zobecnit na grafy, které nejsou rovinné.

Jestliže G je graf, který lze vložit do orientovatelného povrchu S , pak existuje Riemannova metrika d konstantní křivosti na S a kružnice složená v ( S , d ) , jejíž graf tečnosti je izomorfní k G. Pokud je S uzavřený ( kompaktní a nemá žádnou hranici ) a G  je triangulace S , pak ( S , d ) a balení jsou jedinečné až do konformní ekvivalence. Jestliže S  je koule, pak konformní ekvivalence je ekvivalence až do Möbiových transformací; pokud je to torus, tak až do násobení konstantou a izometriemi; pokud je rod povrchu alespoň 2, až do izometrie.

Další zobecnění teorému kružnice zahrnuje nahrazení podmínky tečnosti určením úhlu průsečíku mezi kružnicemi odpovídajícími sousedním vrcholům. Zejména existuje následující elegantní verze této věty. Předpokládejme , že G je konečný 3-souvislý rovinný graf (jinými slovy polyedrický graf ), pak existuje dvojice kruhových obalů tak, že graf průsečíku jednoho obalu je izomorfní k G a graf průniku druhého je izomorfní. k rovinnému duálnímu grafu G. Navíc pro jakýkoli vrchol v G a plochu k němu přiléhající se kružnice odpovídající vrcholu v první výplni protíná v pravém úhlu s kružnicí odpovídající ploše druhé výplně [2] . Například použití tohoto výsledku na graf čtyřstěnu dává pro jakékoli čtyři párové tečné kružnice druhou sadu čtyř vzájemně tečných kružnic, z nichž každá je ortogonální ke třem z první sady [3] . Další zobecnění lze získat nahrazením úhlu průsečíku inverzní vzdáleností [4] .

Další zobecnění umožňuje použití jiných tvarů než kruhů. Předpokládejme, že G = ( V , E ) je konečný rovinný graf a každý vrchol v z G odpovídá obrazci , který je homeomorfní pro uzavřený jednotkový disk a jehož hranice je hladká. Pak je na rovině balení takové, že tehdy a jen tehdy a pro každé se soubor získá pohybem a změnou měřítka. (Všimněte si, že původní teorém o balení kruhu má tři parametry vrcholu, z nichž dva určují střed příslušné kružnice a jeden určuje poloměr a pro každou hranu existuje jedna rovnice. To platí i pro toto zobecnění.) Jeden důkaz toto zobecnění je získáno použitím původního důkazu Koebeho [5] a věty Brandta [6] a Harringtona [7] , která uvádí, že jakákoli konečná spojená doména je konformně ekvivalentní ploché oblasti, jejíž hranice komponent mají specifické tvary až do translace a škálování.

Vztah k teorii konformních zobrazení

Konformní mapování mezi dvěma otevřenými podmnožinami roviny nebo prostoru s vyšší dimenzí je spojité a zachovává úhly mezi libovolnými dvěma křivkami. Riemannův teorém mapování , formulovaný Riemannem v roce 1851, uvádí, že pro jakékoli dva otevřené topologické disky v rovině existuje konformní mapování z jednoho disku na druhý.

Konformní mapování má uplatnění při konstrukci výpočetních sítí , mapových projekcích a dalších oblastech. Není však vždy snadné sestavit konformní mapování mezi dvěma danými oblastmi výslovně [8] .

Na konferenci v roce 1985 William Thurston navrhl, že k aproximaci konformního zobrazení lze použít kruhové balení. Přesněji řečeno, Thurston použil kruhová balení k nalezení konformního zobrazení libovolného otevřeného (topologického) disku A do nitra kruhu. Zobrazení z topologického disku na jiný disk B pak lze nalézt superpozicí zobrazení z A na kružnici a inverzního zobrazení k zobrazení B na kružnici [9] .

Thurstonovou myšlenkou bylo zkonstruovat skupinu kružnic o nějakém malém poloměru r ve formě šestiúhelníkového obkladu [10] na rovině uvnitř oblasti A , přičemž poblíž hranice A zůstal úzký pruh , ve kterém by byla ještě jedna kružnice tohoto poloměru nelze umístit. Potom se z grafu průsečíku kružnice sestaví maximální rovinný graf G a přidá se jeden další vrchol vedle všech kružnic na hranici obalu. Pomocí teorému o naplnění kružnice lze tento rovinný graf znázornit uspořádáním kružnic C , ve kterém jsou všechny hrany (včetně hran dopadajících na hraniční vrcholy) reprezentovány tečností kružnic. Kruhy z obalu A odpovídají jedna ku jedné kružnicím z C , kromě hraničního kruhu C , který odpovídá hranici A . Tato korespondence může být použita ke konstrukci spojitého mapování od A do C , ve kterém je každý kruh a každá mezera mezi třemi kruhy mapována z jednoho balení do druhého pomocí Möbiovy transformace . Thurston navrhl, že jak poloměr r inklinuje k nule, zobrazení z A do C , konstruované tímto způsobem, inklinuje ke konformní funkci, která je dána Riemannovou větou [9] .

Thurstonův dohad byl prokázán Rodinem a Sullivanem [11] . Přesněji ukázali, že jak n směřuje k nekonečnu, funkce f n získaná Thurstonovou metodou konverguje rovnoměrně na kompaktních podmnožinách A z balení po kružnicích o poloměru 1/ n ke konformnímu zobrazení od A do C [9] .

Navzdory potvrzení Thurstonovy domněnky je praktické použití této metody ztíženo složitostí konstrukce kruhových obalů a relativně pomalou konvergencí. Tuto metodu však lze s úspěchem použít v případě nejednoduše spojených domén a při volbě počátečních aproximací pro numerické metody, které počítají Schwartz-Christoffelova zobrazení  - poněkud odlišná metoda pro konstrukci konformních zobrazení polygonálních domén [9] .

Aplikace teorému o balení kruhu

Věta o balení kruhu je užitečným nástrojem pro studium různých problémů v planimetrii, konformních zobrazeních a rovinných grafech. Elegantní důkaz věty o rozdělení rovinného grafu , původně dokázané Liptonem a Tarjanem [12] , je získán pomocí věty o balení kruhu [13] . Další aplikací teorému o balení kruhu je dokázat tvrzení, že nestranné limity rovinných grafů s omezeným stupněm jsou téměř vždy rekurzivní [14] .

Další aplikace jsou derivace pro čas náhodného průchodu grafem [15] a odhad maximální vlastní hodnoty grafů ohraničeného rodu [16] .

Ve vizualizaci grafů se kruhové balení používá k nalezení reprezentace rovinného grafu s omezeným rozlišením [17] a s omezeným počtem sklonů [18] .

Důkaz věty

Existuje mnoho dobře známých důkazů teorému o balení kruhu. Původní důkaz Paula Koebeho je založen na jeho větě o konformní parametrizaci, která říká, že konečně spojená doména je konformně ekvivalentní kružnici. Existuje několik různých známých topologických důkazů. Thurstonův důkaz je založen na Brouwerově teorému o pevném bodě .

Existuje také důkaz pomocí diskrétní verze Perronovy metody pro konstrukci řešení Dirichletova problému . Yves Colin de Verdière dokázal [19] existenci kruhového balení jako minimalizátoru konvexní funkce na některých konfiguračních prostorech.

Důsledky

Fareeův teorém , který říká, že jakýkoli graf, který lze znázornit bez průsečíků v rovině pomocí zakřivených hran, lze také nakreslit bez průsečíků pomocí úseček, je jednoduchým důsledkem teorému o balení kružnic – umístění vrcholů do středů kružnic. a nakreslením liniových segmentů spojujících dotýkající se kružnice získáme zobrazení s hranami ve formě segmentů.

Striktní verze balící věty říká, že každý polyedrický graf a jeho duální graf mohou být reprezentovány dvěma kruhy, takže dva tečné kruhy představují hranu základního grafu a další dva tečné kruhy představují hranu duálu. graf se protínají v pravém úhlu. Tento typ obalu lze použít ke konstrukci konvexního mnohostěnu , který je reprezentován daným grafem a má polovepsanou kouli , kouli tečnou ke všem hranám mnohostěnu . Naopak, má-li mnohostěn polovepsanou kouli, pak kružnice tvořené průsečíkem koule s plochami mnohostěnu a kružnice tvořené horizonty koule, které jsou viditelné z vrcholů mnohostěnu, tvoří dvojité balení.

Algoritmické aspekty

Collins a Stephenson [20] popsali numerický relaxační algoritmus pro nalezení kruhových obalů založený na myšlenkách Williama Thurstona . Verze problému se zabalením kruhu, kterou řeší, bere jako vstup rovinný graf, ve kterém jsou všechny vnitřní plochy trojúhelníky a všechny vnější vrcholy jsou označeny kladnými čísly. Algoritmus poskytuje soubor kružnic, jejichž tečné body reprezentují daný graf a pro které mají kružnice reprezentující vnější vrcholy poloměr daný ve vstupu. Jak navrhli, klíč k problému spočívá v počátečním výpočtu poloměrů těsnicích kružnic. Pokud jsou známy poloměry, není obtížné vypočítat geometrické polohy kružnic. Začnou zkušebními rádiusy, které neodpovídají skutečným sadám, a poté projdou následujícími kroky:

  1. Zvolme si vnitřní vrchol vstupního grafu, tomuto vrcholu odpovídá nějaká kružnice, kterou budeme označovat v . Sousední vrcholy odpovídají lalokům , tj. kružnicím tečným k vybrané kružnici. Nechť k  je počet okvětních lístků.
  2. Vypočítejte celkový úhel θ, který překrývá k sousedních kružnic kolem kružnice v , pokud jsou umístěny blízko sebe a dotýkají se středové kružnice.
  3. Vypočítejte průměrný poloměr r s pro okvětní lístky tak, aby k kružnic o poloměru r s překrývalo stejný úhel θ daný sousedy v .
  4. Nastavte nový poloměr r n pro v takový, aby se k kružnic o průměrném poloměru překrývalo přesně o 2π.

Každý z těchto kroků lze provést pomocí jednoduchých trigonometrických výpočtů, a jak zdůraznili Collins a Stephenson, systém poloměrů konverguje k jedinému pevnému bodu , pro který jsou všechny krycí úhly 2π. Jakmile se systém poloměrů sblíží, mohou být kruhy umístěny jeden po druhém, v každém kroku pomocí polohy a poloměrů dvou sousedních kruhů k výpočtu středu každého úspěšného kruhu.

Mohar [21] popisuje podobnou iterativní techniku ​​pro nalezení shluků polyedrického grafu a jeho duálu, ve kterém se duální cykly protínají v pravých úhlech s pod nimi ležícími kružnicemi. Dokázal, že metoda funguje v polynomiálním čase v počtu kružnic a v log 1/ε, kde ε je hranice vzdáleností od středů a rozdíl mezi poloměry vypočítaného těsnění a optimálního těsnění.

Historie

Větu o balení kruhu poprvé dokázal Paul Koebe [5] .

William Thurston [1] znovu objevil teorém o balení kruhu a všiml si, že vyplývá z práce E. M. Andreeva. Thurston také navrhl schéma pro použití teorému o balení kruhu k získání homeomorfismu spojené množiny v rovině k vnitřku jednotkové kružnice. Thurstonova domněnka o balení kruhu  je předpokladem, že homeomorfismus konverguje k Riemannově mapě , protože poloměry mají tendenci k nule. Thurstonův dohad byl později prokázán Burtonem Rodinem a Dennisem Sullivanem [11] . To vedlo k četným studiím o zobecněních teorému o balení kruhu, stejně jako studiím vztahů s konformním zobrazením a aplikací teorému.

Viz také

Poznámky

  1. ↑ 1 2 Thurston, 1978-1981 .
  2. ↑ Brightwell, Scheinerman, 1993 , s. 214-229.
  3. ↑ Coxeter, 2006 , str. 109-114.
  4. ↑ Bowers, Stephenson, 2004 , s. 78-82.
  5. ↑ 1 2 Koebe, 1936 , str. 141-164.
  6. ↑ Brandt, 1980 .
  7. ↑ Harrington, 1982 , s. 39-53.
  8. ↑ Stephenson, 1999 , s. 551-582.
  9. ↑ 1 2 3 4 Stephenson, 1999 .
  10. ↑ Pokud středy kruhů tvoří pravoúhlou mřížku, obal se nazývá čtvercový. Pokud středy kruhů tvoří trojúhelníkovou mřížku, nazývá se balení šestiúhelníkové.
  11. ↑ 1 2 Rodin a Sullivan 1987 , str. 349-360.
  12. ↑ Lipton, Tarjan, 1979 .
  13. ↑ Miller, Teng, Thurston, Vavasis, 1997 , str. 1-29.
  14. ↑ Benjamini, Schramm, 2001 .
  15. ↑ Jonnason, Schramm, 2000 .
  16. ↑ Kelner, 2006 , str. 882-902.
  17. ↑ Malitz a Papakostas 1994 , str. 172-183.
  18. ↑ Keszegh, Pach, Pálvölgyi, 2011 , str. 293-304.
  19. ↑ Verdière, 1991 , s. 655-669.
  20. ↑ Collins, Stephenson, 2003 , str. 233-256.
  21. ↑ Mohar, 1993 , str. 257-263.

Literatura

Odkazy

 Balicí úkoly
Balící kruhy
Balení balónků
Další balíčky
Hádanka