Ympyräpakkauslause

Ympyrän pakkauslause (tunnetaan myös nimellä Koebe-Andreev-Thurston -lause ) kuvaa kuinka ympyröitä voidaan koskettaa, jos niillä ei ole yhteisiä sisäpisteitä. Ympyröiden pakkauksen leikkausgraafi (jota kutsutaan joskus tangenttigraafiksi ) on graafi , jonka kärjet vastaavat ympyröitä ja jonka reunat vastaavat tangenttipisteitä. Jos ympyrät on pakattu tasolle (tai vastaavasti pallolle), niin niiden leikkauskuvaajaa kutsutaan kolikkograafiksi . Kolikkokaaviot ovat aina yhdistettyjä, yksinkertaisia ​​ja tasomaisia . Ympyrän pakkauslause sanoo, että myös päinvastoin on totta:

Ympyräpakkauslause : Jokaiselle yhdistetylle yksinkertaiselle tasograafille G on tasossa ympyräpakkaus, jonka leikkauskäyrä on isomorfinen G:n kanssa .

Ainutlaatuisuus

Graafia G kutsutaan kolmiotasomaiseksi (tai maksimaaliseksi tasomaiseksi), jos se on tasomainen ja millä tahansa G :n palloon upottamisen komplementin yhdistetyllä komponentilla on tasan kolme reunaa rajalla, tai toisin sanoen, jos G on yksi. -ulotteinen virittävä puu yksinkertaisesta kompleksista , joka on homeomorfinen pallolle. Mikä tahansa kolmiomainen tasograafi G on yhdistetty ja yksinkertainen, joten ympyräpakkauslause takaa sellaisen pakkauksen olemassaolon, jonka tangenttigraafi on isomorfinen G :n kanssa . Tällaisen graafin G on oltava äärellinen, jotta vastaavalla pakkauksella on äärellinen määrä ympyröitä. Kuten seuraavassa lauseessa todetaan, mikä tahansa maksimaalinen tasograafi voi vastata enintään yhtä pakkausta.

Koebe–Andreev–Thurston-lause : Jos G on äärellinen kolmiomainen tasograafi, niin ympyräpakkaus, jonka tangenttigraafi on (isomorfinen) G :n kanssa, on ainutlaatuinen aina Möbius-muunnoksiin ja suorien heijastuksiin asti.

Thurston [1] huomautti, että tämä ainutlaatuisuus on seurausta Mostow'n jäykkyyslauseesta . Taso, johon ympyrät pakataan, voidaan nähdä Poincarén mallin rajana puoliavaruudessa . Tästä näkökulmasta mikä tahansa ympyrä on tason raja hyperbolisessa avaruudessa. Jokainen ympyräpakkaus voidaan liittää joukkoon ei-leikkaavia tasoja, samoin kuin toiseen joukkoon ei-leikkautuvia tasoja, jotka määritetään kolmen tiivistysympyrän välisillä kolmioalueilla. Tasot eri joukoista leikkaavat suorassa kulmassa ja vastaavat heijastusryhmän generaattoreita , jonka perusaluetta voidaan pitää hyperbolisena moninaisena . Mostow'n jäykkyyslauseen mukaan tämän alueen hyperbolinen rakenne on yksilöllisesti määritelty hyperbolisen avaruuden isometreihin asti . Nämä isometriat, kun niitä tarkastellaan Poincarén mallin rajalla tapahtuvan toiminnan kannalta, muuttuvat Möbius-muunnoksiksi.

On olemassa myös alkeistodistus, joka perustuu maksimiperiaatteeseen ja havaintoon, että kolmen keskenään tangentin ympyrän keskipisteitä yhdistävässä kolmiossa yhden ympyrän keskipisteessä olevaan kärkeen muodostuva kulma pienenee monotonisesti sen säteen kasvaessa ja kasvaessa. monotonisesti, kun mikä tahansa kahdesta muusta ympyrästä kasvaa. Kun on annettu kaksi pakkausta samalle graafille G , heijastuksia ja Möbius-muunnoksia voidaan käyttää saamaan ulommat ympyrät vastaavat toisiaan ja niillä on samat säteet. Olkoon v sitten G :  n sisäinen kärkipiste, jonka kaksipakatut ympyrät ovat koot mahdollisimman kaukana toisistaan. Toisin sanoen v on valittu maksimoimaan kahden paketin ympyröiden säteiden suhde r 1 / r 2 . Tästä seuraa, että jokaiselle G :n kolmiopinnalle, joka sisältää v :n, kulma v : tä vastaavan ympyrän keskipisteen kärjen kanssa on pienempi tai yhtä suuri kuin toisen tiivisteen kulma, ja yhtä suuri kuin kaksi muuta ympyrät muodostavat kolmion, jolla on sama suhde r 1 / r 2 toisen tiivisteen säteet. Mutta kaikkien kolmion keskustaa ympäröivien kolmioiden kulmien summan on oltava 2π molemmissa täytteissä, joten kaikilla v:n viereisillä pisteillä on oltava sama suhde kuin v :llä itsellään . Soveltamalla samaa päättelyä muihin ympyröihin käy ilmi, että molemmissa pakkauksissa olevilla ympyröillä on sama suhde. Mutta ulommat ympyrät muunnetaan suhteiksi 1, jolloin r 1 / r 2 = 1 ja molemmilla paketeilla on samat säteet kaikille ympyröille.

Ympyrän pakkauslauseen yleistykset

Ympyräpakkaus voidaan yleistää kuvaajiksi, jotka eivät ole tasomaisia.

Jos G on graafi, joka voidaan upottaa suuntautuvaan pintaan S , niin on olemassa vakiokaarevuuden omaava Riemannin metriikka d S :llä ja ympyrä, joka pakautuu kohtaan ( S , d ) , jonka tangenttigraafi on isomorfinen G :n kanssa. Jos S on suljettu ( kompakti ja sillä ei ole rajaa ) ja G on S :  n kolmio , niin ( S , d ) ja pakkaus ovat ainutlaatuisia konformiseen ekvivalenssiin asti. Jos S  on pallo, niin konforminen ekvivalenssi on ekvivalenssi Möbius-muunnoksiin asti; jos se on torus, niin vakiolla ja isometrioilla kertomiseen asti; jos pinnan suku on vähintään 2, isometriaan asti.

Toinen ympyrän pakkauslauseen yleistys sisältää tangenttiehdon korvaamisen määrittämällä naapuripisteitä vastaavien ympyröiden välisen leikkauskulman. Tästä lauseesta on erityisesti seuraava tyylikäs versio. Oletetaan , että G on äärellinen 3-kytkentäinen tasograafi (toisin sanoen monitahoinen graafi ), silloin on olemassa pari ympyräpakkauksia siten, että yhden pakkauksen leikkauskuvaaja on isomorfinen G :n kanssa ja toisen leikkauskuvaaja on isomorfinen G : n tasomaiseen kaksoisgraafiin . Lisäksi minkä tahansa G :n kärjen ja sen vieressä olevan pinnan kohdalla ensimmäisen pakkauksen kärkeä vastaava ympyrä leikkaa suorassa kulmassa toisen tiivisteen pintaa vastaavan ympyrän kanssa [2] . Esimerkiksi tämän tuloksen soveltaminen tetraedrin kuvaajaan antaa millä tahansa neljällä parittaisella tangenttiympyrällä toisen neljän toisiaan tangentin ympyrän joukon, joista jokainen on ortogonaalinen kolmeen ensimmäisestä joukosta [3] . Lisäyleistys saadaan korvaamalla leikkauskulma käänteisellä etäisyydellä [4] .

Toinen yleistys sallii muiden muotojen kuin ympyröiden käytön. Oletetaan, että G = ( V , E ) on äärellinen tasograafi ja jokainen G :n kärki v vastaa kuvaa , joka on homeomorfinen suljetun yksikkökiekon kanssa ja jonka raja on sileä. Sitten on tasossa pakkaus siten, että jos ja vain jos ja jokaiselle joukko saadaan siirtämällä ja skaalaamalla. (Huomaa, että alkuperäisessä ympyräpakkauslauseessa on kolme kärkiparametria, joista kaksi määrittää vastaavan ympyrän keskipisteen ja yksi säteen, ja jokaiselle reunalle on yksi yhtälö. Tämä pätee myös tähän yleistykseen.) Yksi todiste tämä yleistys saadaan käyttämällä Koeben [5] alkuperäistä todistetta sekä Brandtin [6] ja Harringtonin [7] lausetta, jonka mukaan mikä tahansa äärellinen yhdistetty alue on konformisesti ekvivalentti tasaiselle alueelle, jonka komponenttien rajat ovat muodoltaan tietyt käännökseen ja skaalaus.

Suhde konformisten kartoitusten teoriaan

Konforminen kartoitus korkeamman ulottuvuuden tason tai avaruuden kahden avoimen osajoukon välillä on jatkuva ja säilyttää minkä tahansa kahden käyrän väliset kulmat . Riemannin kartoituslause , jonka Riemannin muotoili vuonna 1851, sanoo, että kahdelle avoimelle topologiselle levylle tasossa on olemassa konforminen kartoitus levyltä toiselle.

Konformaalisilla kartoituksella on sovelluksia laskennallisten verkkojen , karttaprojektioiden ja muiden alueiden rakentamisessa. Aina ei kuitenkaan ole helppoa rakentaa konformista kartoitusta kahden tietyn alueen välille eksplisiittisesti [8] .

Vuonna 1985 pidetyssä konferenssissa William Thurston ehdotti, että ympyräpakkausta voitaisiin käyttää likimääräiseen yhdenmukaisuuteen. Tarkemmin sanottuna Thurston käytti ympyräpakkauksia löytääkseen mielivaltaisen avoimen (topologisen) levyn A konformisen kartoituksen ympyrän sisäpuolelle. Kuvaus topologisesta levystä toiselle levylle B voidaan sitten löytää superpositiolla A :sta ympyrään ja käänteiskuvauksella B :n kuvaamiseen ympyrään [9] .

Thurstonin ideana oli rakentaa jonkin pienen säteen r ympyröiden paketti kuusikulmaisen laatoituksen muodossa [10] alueen A sisäpuolelle tasolle jättäen kapea kaistale lähellä A :n rajaa , jossa vielä yksi tämän säteen ympyrä. ei voida sijoittaa. Sitten muodostetaan maksimitasograafi G ympyränleikkausgraafista ja lisätään yksi ylimääräinen huippupiste kaikkien pakkausrajan ympyröiden viereen. Ympyräpakkauslauseen mukaan tämä tasograafi voidaan esittää ympyräpakkauksella C , jossa kaikki reunat (mukaan lukien reunapisteisiin kohdistuvat reunat) esitetään ympyröiden tangentsilla. Pakkauksen A ympyrät vastaavat yksitellen ympyröitä kohdasta C , paitsi rajaympyrä C , joka vastaa A :n rajaa . Tämän vastaavuuden avulla voidaan rakentaa jatkuva kuvaus A :sta C :hen, jossa jokainen ympyrä ja jokainen kolmen ympyrän välinen rako kartoitetaan pakkauksesta toiseen Möbius-muunnoksen avulla . Thurston ehdotti, että koska säde r pyrkii nollaan, tällä tavalla muodostettu kartoitus A :sta C :hen pyrkii konformiseen funktioon, joka saadaan Riemmannin lauseella [9] .

Rodin ja Sullivan vahvistivat Thurstonin oletuksen [11] . Tarkemmin sanottuna he osoittivat, että kun n pyrkii äärettömyyteen, Thurstonin menetelmällä saatu funktio f n konvergoi tasaisesti kompakteissa osajoukkoissa A säteisten 1/ n ympyröiden pakkaamisesta konformiseen mappaukseen A :sta C :hen [9] .

Huolimatta Thurstonin olettamuksesta, tämän menetelmän käytännön soveltamista vaikeuttaa ympyräpakkausten rakentamisen monimutkaisuus ja suhteellisen hidas konvergenssi. Tätä menetelmää voidaan kuitenkin käyttää menestyksekkäästi ei- yksinkertaisesti yhdistettyjen alueiden tapauksessa ja alkuperäisten approksimaatioiden valinnassa numeerisille menetelmille, jotka laskevat Schwartz-Christoffel-kartoituksia - hieman erilainen menetelmä monikulmioalueiden  konformisten kuvausten muodostamiseen [9] .

Ympyrän pakkauslauseen sovellukset

Ympyräpakkauslause on hyödyllinen työkalu erilaisten planimetrian, konformisten mappausten ja tasograafien ongelmien tutkimiseen. Liptonin ja Tarjanin [12] alunperin todistaman tasograafin osiointilauseen tyylikäs todistus saadaan käyttämällä ympyrän pakkauslausetta [13] . Toinen ympyräpakkauslauseen sovellus on todistaa väite, että tasograafien, joilla on rajallinen aste, puolueettomat rajat ovat lähes aina rekursiivisia [14] .

Muita sovelluksia ovat graafin satunnaisen läpikulkuajan johtaminen [15] ja rajatun suvun graafien enimmäisominaisarvon estimoiminen [16] .

Graafisten visualisoinnissa ympyräpakkausta käytetään tasokuvaajan esityksen löytämiseen rajoitetulla resoluutiolla [17] ja rajoitetulla määrällä kaltevia [18] .

Lauseen todistus

Ympyräpakkauslauseesta on monia tunnettuja todisteita. Paul Koeben alkuperäinen todistus perustuu hänen konformiseen parametrisointilauseeseensa, jonka mukaan äärellisesti yhdistetty alue vastaa konformisesti ympyrää. On olemassa useita erilaisia ​​tunnettuja topologisia todisteita. Thurstonin todistus perustuu Brouwerin kiinteän pisteen lauseeseen .

On myös olemassa todistus, joka käyttää Perronin menetelmän erillistä versiota ratkaisun rakentamiseen Dirichlet-ongelmaan . Yves Colin de Verdière osoitti [19] ympyräpakkauksen olemassaolon konveksin funktion minimoijana joissakin konfiguraatioavaruuksissa.

Seuraukset

Fareen lause , jonka mukaan mikä tahansa graafi, joka voidaan esittää ilman leikkauspisteitä tasossa kaarevien reunojen avulla, voidaan myös piirtää ilman leikkauspisteitä suorasegmenteillä, on yksinkertainen seuraus ympyrän pakkausteoreemasta - pisteiden sijoittamisesta ympyröiden keskipisteisiin. ja piirtämällä viivasegmenttejä, jotka yhdistävät koskettavat ympyrät, saamme esityksen, jossa reunat ovat segmenttien muodossa.

Pakkauslauseen tiukka versio sanoo, että mikä tahansa monitahoinen graafi ja sen duaaligraafi voidaan esittää kahdella ympyrän pakkauksella siten, että kaksi tangenttiympyrää edustavat perusgraafin reunaa ja kaksi muuta tangenttiympyrää duaalin reunaa. kaavio leikkaa suorassa kulmassa. Tämän tyyppistä pakkausta voidaan käyttää kuperan monitahoisen rakentamiseen , joka on esitetty tietyllä graafilla ja jossa on puolikirjoitettu pallo , pallo, joka tangentti monitahoisen kaikkia reunoja . Päinvastoin, jos monitaholla on puolikirjoitettu pallo, muodostuvat ympyrät, jotka muodostuvat pallon leikkauspisteestä monitahoisen pinnan kanssa ja pallon horisonttien muodostamat ympyrät, jotka näkyvät monitahoisen pisteistä. kaksoispakkaukset.

Algoritmiset näkökohdat

Collins ja Stephenson [20] kuvasivat William Thurstonin ideoihin perustuvan numeerisen relaksaatioalgoritmin ympyräpakkausten löytämiseksi . Ympyräpakkausongelman versio, jonka he ratkaisevat, ottaa syötteenä tasograafin, jossa kaikki sisäpinnat ovat kolmioita ja kaikki ulkopisteet on merkitty positiivisilla luvuilla. Algoritmi tuottaa pakkauksen ympyröitä, joiden tangenttipisteet edustavat annettua kuvaajaa ja joiden ulompia pisteitä edustavilla ympyröillä on syötteessä annettu säde. Kuten he ehdottivat, ongelman avain piilee tiivistysympyröiden säteiden alustavassa laskennassa. Jos säteet tunnetaan, ympyröiden geometristen paikkojen laskeminen ei ole vaikeaa. Ne alkavat kokeilusäteillä, jotka eivät vastaa oikeita paketteja, ja jatkavat sitten seuraavien vaiheiden läpi:

  1. Valitaan sisääntulograafin sisäinen kärki, tämä kärki vastaa jotakin ympyrää, jota merkitsemme v . Naapuripisteet vastaavat keiloja eli ympyröitä, jotka tangentit valitun ympyrän kanssa. Olkoon k  terälehtien lukumäärä.
  2. Laske kokonaiskulma θ, jonka päällekkäin tulee k vierekkäistä ympyrää ympyrän v ympärillä , jos ne ovat lähellä toisiaan ja jotka koskettavat keskiympyrää.
  3. Laske terälehtien keskimääräinen säde r s siten, että k ympyrää, joiden säde on r s , menevät päällekkäin naapureiden v antaman kulman θ kanssa .
  4. Aseta v :lle uusi säde r n siten, että k keskisäteistä ympyrää menevät päällekkäin täsmälleen 2π:n kanssa.

Jokainen näistä vaiheista voidaan tehdä yksinkertaisilla trigonometrisilla laskelmilla, ja kuten Collins ja Stephenson ovat huomauttaneet, sädejärjestelmä konvergoi yhteen kiinteään pisteeseen , jonka kaikki peittokulmat ovat 2π. Kun sädejärjestelmä on lähentynyt, ympyrät voidaan sijoittaa yksi kerrallaan jokaisessa vaiheessa käyttämällä kahden vierekkäisen ympyrän sijaintia ja säteitä kunkin onnistuneen ympyrän keskipisteen laskemiseksi.

Mohar [21] kuvaa samanlaista iteratiivista tekniikkaa polyhedraalisen graafin ja sen duaalin pakkausten löytämiseksi , jossa kaksoissyklit leikkaavat suorassa kulmassa alla olevien ympyröiden kanssa. Hän osoitti, että menetelmä toimii polynomiajassa ympyröiden lukumäärässä ja log 1/ε:ssä, jossa ε on etäisyyksien raja keskipisteistä sekä lasketun pakkauksen ja optimaalisen pakkauksen säteiden välinen ero.

Historia

Ympyräpakkauslauseen osoitti ensimmäisenä Paul Koebe [5] .

William Thurston [1] löysi uudelleen ympyrän pakkauslauseen ja huomasi sen olevan seurausta E. M. Andreevin työstä. Thurston ehdotti myös kaaviota ympyrän pakkauslauseen käyttämiseksi yksikköympyrän sisäpuolen tasossa olevan yhdistetyn joukon homeomorfismin saamiseksi. Thurstonin ympyräpakkausoletus  on oletus, että homeomorfismi konvergoi Riemannin karttaan säteiden pyrkiessä nollaan. Burton Rodin ja Dennis Sullivan vahvistivat myöhemmin Thurstonin oletuksen [11] . Tämä on johtanut lukuisiin tutkimuksiin ympyrän pakkauslauseen yleistyksistä sekä tutkimuksiin suhteista konformisiin mappauksiin ja lauseen sovelluksiin.

Katso myös

Muistiinpanot

  1. ↑ 1 2 Thurston, 1978-1981 .
  2. ↑ Brightwell, Scheinerman, 1993 , s. 214-229.
  3. ↑ Coxeter, 2006 , s. 109-114.
  4. ↑ Bowers, Stephenson, 2004 , s. 78-82.
  5. ↑ 1 2 Koebe, 1936 , s. 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. ↑ Jos ympyröiden keskipisteet muodostavat suorakaiteen hilan, pakkausta kutsutaan neliöksi. Jos ympyröiden keskipisteet muodostavat kolmiomaisen hilan, tiivistettä kutsutaan kuusikulmioksi.
  11. ↑ 1 2 Rodin ja Sullivan 1987 , s. 349-360.
  12. ↑ Lipton, Tarjan, 1979 .
  13. ↑ Miller, Teng, Thurston, Vavasis, 1997 , s. 1-29.
  14. ↑ Benjamini, Schramm, 2001 .
  15. ↑ Jonnason, Schramm, 2000 .
  16. ↑ Kelner, 2006 , s. 882-902.
  17. ↑ Malitz ja Papakostas 1994 , s. 172-183.
  18. ↑ Keszegh, Pach, Pálvölgyi, 2011 , s. 293-304.
  19. ↑ Verdière, 1991 , s. 655-669.
  20. ↑ Collins, Stephenson, 2003 , s. 233-256.
  21. ↑ Mohar, 1993 , s. 257-263.

Kirjallisuus

Linkit

 Pakkaustehtävät
Pakkaa ympyrät
Ilmapallon pakkaus
Muut paketit
Palapeli