Cirkelpackningssats

Cirkelpackningssatsen (även känd som Koebe-Andreev-Thurston-satsen ) beskriver hur cirklar kan beröras om de inte har några gemensamma inre punkter. En skärningsgraf (kallas ibland en tangensgraf ) av en packning av cirklar är en graf vars hörn motsvarar cirklar och vars kanter motsvarar tangenspunkter. Om cirklarna är packade på ett plan (eller, motsvarande, på en sfär), kallas deras skärningsdiagram en myntgraf . Myntgrafer är alltid sammankopplade, enkla och plana . Cirkelpackningssatsen säger att det omvända också är sant:

Cirkelpackningssats : För varje ansluten enkel plan graf G , finns det en cirkelpackning i planet vars skärningsgraf är isomorf med G.

Unikhet

En graf G kallas triangulerad plan (eller maximal planar) om den är plan och någon sammankopplad komponent av komplementet av inbäddningen av G i en sfär har exakt tre kanter på gränsen, eller, med andra ord, om G är en etta -dimensionellt spännande träd av ett enkelt komplex som är homeomorft till en sfär. Varje triangulerad plan graf G är sammankopplad och enkel, så cirkelpackningssatsen garanterar existensen av en packning vars tangensgraf är isomorf till G . En sådan graf G måste vara ändlig, så att motsvarande packning kommer att ha ett ändligt antal cirklar. Som följande sats säger, kan vilken maximal plan graf som helst motsvara högst en packning.

Koebe–Andreev–Thurstons teorem : Om G är en finit triangulerad plan graf, så är en cirkelpackning vars tangensgraf är (isomorf till) G unik upp till Möbius-transformationer och reflektioner med avseende på linjer.

Thurston [1] noterade att denna unikhet är en följd av Mostows stelhet om stelhet . Planet i vilket cirklarna är packade kan ses som gränsen för Poincaré-modellen i ett halvutrymme . Ur denna synvinkel är vilken cirkel som helst gränsen för ett plan i det hyperboliska rymden. Varje packning av cirklar kan associeras med en uppsättning icke-korsande plan, såväl som en andra uppsättning av icke-korsande plan definierade av triangulära områden mellan de tre packningscirklarna. Plan från olika uppsättningar skär varandra i räta vinklar och motsvarar generatorerna av reflektionsgruppen , vars grundläggande domän kan betraktas som en hyperbolisk mångfald . Genom Mostows styvhetsteorem är den hyperboliska strukturen för denna domän unikt definierad upp till isometrier av det hyperboliska rummet. Dessa isometrier, när de betraktas i termer av verkan på gränsen för Poincaré-modellen, förvandlas till Möbius-transformationer.

Det finns också ett elementärt bevis baserat på maximiprincipen och på observationen att i en triangel som förbinder mitten av tre ömsesidigt tangentiella cirklar, minskar vinkeln som bildas vid spetsen i centrum av en av cirklarna monotont när dess radie ökar och ökar monotont när någon av de andra två cirklarna ökar. Givet två packningar för samma graf G kan reflektioner och Möbiustransformationer användas för att få de yttre cirklarna i de två packningarna att motsvara varandra och ha samma radier. Låt sedan v  vara ett inre hörn av G där de tvåpackade cirklarna har storlekar så långt ifrån varandra som möjligt. Det vill säga, v väljs för att maximera förhållandet r 1 / r 2 av radierna för cirklarna i de två paketen. Härav följer att för varje triangulär yta av G som innehåller v , är vinkeln med spetsen på cirkelcentrum som motsvarar v i den första packningen mindre än eller lika med vinkeln i den andra packningen, med likhet endast om de andra två cirklar bildar en triangel med samma förhållande r 1 / r 2 radier av den andra packningen. Men summan av vinklarna för alla trianglar som omger triangelns centrum måste vara 2π i båda packningarna, så att alla hörn som gränsar till v måste ha samma förhållande som själva v . Om man tillämpar samma resonemang på andra cirklar, visar det sig att alla cirklar i båda paketen har samma relation. Men de yttre cirklarna omvandlas till att ha förhållandet 1, så att r 1 / r 2 = 1 och båda paketen har lika radier för alla cirklar.

Generaliseringar av cirkelpackningssatsen

Cirkelpackning kan generaliseras till grafer som inte är plana.

Om G är en graf som kan bäddas in i en orienterbar yta S , så finns det en Riemannisk metrisk d med konstant krökning på S och en cirkel packad i ( S , d ) vars tangensgraf är isomorf till G. Om S är stängd ( kompakt och har ingen gräns ) och G  är en triangulering av S , då är ( S , d ) och packning unika upp till konform ekvivalens. Om S  är en sfär, så är en konform ekvivalens en ekvivalens upp till Möbiustransformationer; om det är en torus, då upp till multiplikation med en konstant och isometrier; om ytans släkt är minst 2, upp till isometri.

En annan generalisering av cirkelpackningssatsen innebär att tangensvillkoret ersätts genom att specificera skärningsvinkeln mellan cirklar som motsvarar angränsande hörn. I synnerhet finns det följande eleganta version av detta teorem. Anta att G är en ändlig 3-kopplad plan graf (med andra ord en polyedrisk graf ), då finns det ett par cirkelpackningar så att skärningsgrafen för en packning är isomorf till G och skärningsgrafen för den andra är isomorf till G :s plana dubbla graf. Dessutom, för varje vertex i G och en yta intill den, skär cirkeln som motsvarar vertexen i den första packningen i rät vinkel med cirkeln som motsvarar ytan i den andra packningen [2] . Till exempel, att tillämpa detta resultat på en graf av en tetraeder ger, för alla fyra parvisa tangentcirklar, en andra uppsättning av fyra ömsesidigt tangentiella cirklar, som var och en är ortogonal mot tre av den första uppsättningen [3] . En ytterligare generalisering kan erhållas genom att ersätta skärningsvinkeln med ett omvänt avstånd [4] .

En annan generalisering tillåter användning av andra former än cirklar. Antag att G = ( V , E ) är en finit plan graf och varje vertex v i G motsvarar en figur som är homeomorf till den slutna enhetsskivan och vars gräns är jämn. Sedan finns det en packning på planet så att om och bara om och för varje uppsättningen erhålls från genom att flytta och skala. (Observera att den ursprungliga cirkelpackningssatsen har tre vertexparametrar, varav två anger centrum för motsvarande cirkel och en anger radien, och det finns en ekvation för varje kant. Detta gäller även för denna generalisering.) Ett bevis på denna generalisering erhålls genom att använda originalbeviset från Koebe [5] och teorem från Brandt [6] och Harrington [7] som säger att varje ändlig ansluten domän är konformt ekvivalent med en platt domän vars komponentgränser har specifika former upp till translation och skalning.

Samband med teorin om konforma mappningar

En konform mappning mellan två öppna delmängder av ett högre dimensionellt plan eller utrymme är kontinuerlig och bevarar vinklarna mellan två valfria kurvor. Riemanns kartläggningssats , formulerad av Riemann 1851, säger att för två öppna topologiska skivor i planet finns det en konform avbildning från en skiva till den andra.

Konforma mappningar har tillämpningar vid konstruktion av beräkningsnät , kartprojektioner och andra områden. Det är dock inte alltid lätt att konstruera en konform kartläggning mellan två givna regioner explicit [8] .

Vid en konferens 1985 föreslog William Thurston att cirkelpackning kunde användas för att approximera konforma mappningar. Mer exakt använde Thurston cirkelpackningar för att hitta en konform kartläggning av en godtycklig öppen (topologisk) skiva A in i det inre av en cirkel. En mappning från en topologisk skiva till en annan skiva B kan sedan hittas genom överlagring av en mappning från A till en cirkel och en mappning invers till mappningen av B till en cirkel [9] .

Thurstons idé var att konstruera en packning av cirklar med någon liten radie r i form av en hexagonal plattsättning [10] på planet inuti regionen A , vilket lämnar en smal remsa nära gränsen till A , i vilken ytterligare en cirkel med denna radie kan inte placeras. Därefter konstrueras den maximala plana grafen G från cirkelskärningsgrafen och ytterligare en vertex läggs till intill alla cirklar på packningsgränsen. Genom cirkelpackningssatsen kan denna plana graf representeras av en cirkelpackning C där alla kanter (inklusive kanter som faller mot gränsens hörn) representeras av cirklarnas tangens. Cirklarna från packningen A motsvarar en-till-en cirklarna från C , förutom gränscirkeln C , som motsvarar gränsen för A . Denna överensstämmelse kan användas för att konstruera en kontinuerlig mappning från A till C , där varje cirkel och varje gap mellan tre cirklar avbildas från en packning till en annan med hjälp av en Möbius-transformation . Thurston föreslog att när radien r tenderar mot noll, tenderar avbildningen från A till C , konstruerad på detta sätt, till en konform funktion, som ges av Riemanns sats [9] .

Thurstons gissning bevisades av Rodin och Sullivan [11] . Mer exakt visade de att eftersom n tenderar till oändlighet, konvergerar funktionen f n som erhålls med Thurstons metod enhetligt på kompakta delmängder A från en packning med cirklar med radien 1/ n till en konform avbildning från A till C [9] .

Trots bekräftelsen av Thurstons gissning hämmas den praktiska tillämpningen av denna metod av komplexiteten i att konstruera cirkelpackningar och den relativt långsamma konvergensen. Denna metod kan dock användas framgångsrikt i fallet med icke- enkelt anslutna domäner och i valet av initiala approximationer för numeriska metoder som beräknar Schwartz-Christoffel-mappningar  - en något annorlunda metod för att konstruera konforma mappningar av polygonala domäner [9] .

Tillämpningar av cirkelpackningssatsen

Cirkelpackningssatsen är ett användbart verktyg för att studera olika problem inom planimetri, konforma avbildningar och plana grafer. Ett elegant bevis på den plana grafens partitioneringssats , ursprungligen bevisad av Lipton och Tarjan [12] , erhålls med hjälp av cirkelpackningssatsen [13] . En annan tillämpning av cirkelpackningssatsen är att bevisa påståendet att de opartiska gränserna för plana grafer med begränsad grad nästan alltid är rekursiva [14] .

Andra tillämpningar är härledningar för tiden för slumpmässig genomgång av en graf [15] och uppskattning av det maximala egenvärdet för grafer av begränsat släkte [16] .

I grafvisualisering används cirkelpackning för att hitta en representation av en plan graf med begränsad upplösning [17] och med ett begränsat antal lutningar [18] .

Bevis för satsen

Det finns många välkända bevis för cirkelpackningssatsen. Paul Koebes ursprungliga bevis är baserat på hans konforma parametriseringssats som säger att en ändligt ansluten domän är konformt ekvivalent med en cirkel. Det finns flera olika kända topologiska bevis. Thurstons bevis är baserat på Brouwers fixpunktssats .

Det finns också ett bevis som använder en diskret version av Perron-metoden för att konstruera en lösning på Dirichlet-problemet . Yves Colin de Verdière bevisade [19] förekomsten av en cirkelpackning som en minimering av en konvex funktion på vissa konfigurationsutrymmen.

Konsekvenser

Farees sats , som säger att vilken graf som helst som kan representeras utan skärningar i planet med hjälp av böjda kanter, också kan ritas utan skärningspunkter med hjälp av linjesegment, är en enkel konsekvens av cirkelpackningssatsen - att placera hörnen i cirklarnas mittpunkter och rita linjesegment som förbinder de rörande cirklarna, vi får en representation med kanter i form av segment.

En strikt version av packningssatsen säger att vilken polyedrisk graf som helst och dess dubbla graf kan representeras av två packningar av cirklar, så att de två tangentcirklarna representerar en kant på basgrafen och de andra två tangentcirklarna representerar en kant av den dubbla grafen skär i rät vinkel. Denna typ av packning kan användas för att konstruera en konvex polyeder som representeras av en given graf och har en halvinskriven sfär , en sfär som tangerar alla kanter av polyedern . Omvänt, om en polyeder har en halvinskriven sfär, bildas cirklarna som bildas av sfärens skärning med polyederns ytor och cirklarna som bildas av sfärens horisonter, som är synliga från polyederns hörn. dubbla packningar.

Algoritmiska aspekter

Collins och Stephenson [20] beskrev en numerisk avslappningsalgoritm för att hitta cirkelpackningar baserade på idéerna från William Thurston . Den version av cirkelpackningsproblemet de löser tar som indata en plan graf där alla inre ytor är trianglar och alla yttre hörn är märkta med positiva tal. Algoritmen ger en packning av cirklar vars tangentpunkter representerar den givna grafen och för vilka cirklarna som representerar de yttre hörnen har den radie som anges i ingången. Som de föreslog ligger nyckeln till problemet i den initiala beräkningen av packningscirklarnas radier. Om radierna är kända är de geometriska positionerna för cirklarna inte svåra att beräkna. De börjar med provradier som inte matchar riktiga förpackningar och går sedan igenom följande steg:

  1. Låt oss välja en intern vertex för ingångsgrafen, denna vertex motsvarar någon cirkel, som vi kommer att beteckna v . Närliggande hörn motsvarar lober , dvs cirklar som tangerar den valda cirkeln. Låt k  vara antalet kronblad.
  2. Beräkna den totala vinkeln θ som överlappas av k angränsande cirklar runt cirkeln v , om de är placerade nära varandra och som berör den centrala cirkeln.
  3. Beräkna medelradien r s för kronbladen så att k cirklar med radien r s överlappar samma vinkel θ som ges av grannarna v .
  4. Ställ in en ny radie r n för v så att k cirklar med medelradie skulle överlappa exakt 2π.

Vart och ett av dessa steg kan göras med enkla trigonometriska beräkningar, och som Collins och Stephenson har påpekat, konvergerar systemet av radier till en enda fixpunkt för vilken alla täckningsvinklar är 2π. När systemet med radier har konvergerat kan cirklarna placeras en i taget, vid varje steg med hjälp av positionen och radierna för de två intilliggande cirklarna för att beräkna mitten av varje framgångsrik cirkel.

Mohar [21] beskriver en liknande iterativ teknik för att hitta packningar av en polyedrisk graf och dess dubbla där de dubbla cyklerna skär rät vinkel med de underliggande cirklarna. Han bevisade att metoden fungerar i polynomtid i antalet cirklar och i log 1/ε, där ε är gränsen för avstånden från centra och skillnaden mellan radierna för den beräknade packningen och den optimala packningen.

Historik

Cirkelpackningssatsen bevisades först av Paul Koebe [5] .

William Thurston [1] återupptäckte cirkelpackningssatsen och märkte att den följer av E. M. Andreevs arbete. Thurston föreslog också ett schema för att använda cirkelpackningssatsen för att erhålla en homeomorfism av en sammankopplad uppsättning i planet till det inre av enhetscirkeln. Thurstons cirkelpackande gissning  är antagandet att en homeomorfism konvergerar till en Riemann-karta eftersom radierna tenderar mot noll. Thurstons gissning bevisades senare av Burton Rodin och Dennis Sullivan [11] . Detta har lett till ett flertal studier om generaliseringar av cirkelpackningssatsen, såväl som studier om samband med konforma avbildningar och tillämpningar av teoremet.

Se även

Anteckningar

  1. ↑ 1 2 Thurston, 1978-1981 .
  2. ↑ Brightwell, Scheinerman, 1993 , sid. 214-229.
  3. ↑ Coxeter, 2006 , sid. 109-114.
  4. ↑ Bowers, Stephenson, 2004 , sid. 78-82.
  5. ↑ 1 2 Koebe, 1936 , sid. 141-164.
  6. ↑ Brandt, 1980 .
  7. ↑ Harrington, 1982 , sid. 39-53.
  8. ↑ Stephenson, 1999 , sid. 551-582.
  9. ↑ 1 2 3 4 Stephenson, 1999 .
  10. ↑ Om cirklarnas mittpunkter bildar ett rektangulärt gitter kallas packningen kvadratisk. Om cirklarnas mittpunkter bildar ett triangulärt gitter kallas packningen hexagonal.
  11. ↑ 1 2 Rodin och Sullivan 1987 , sid. 349-360.
  12. ↑ Lipton, Tarjan, 1979 .
  13. ↑ Miller, Teng, Thurston, Vavasis, 1997 , sid. 1-29.
  14. ↑ Benjamini, Schramm, 2001 .
  15. ↑ Jonnason, Schramm, 2000 .
  16. ↑ Kelner, 2006 , sid. 882-902.
  17. ↑ Malitz och Papakostas 1994 , sid. 172-183.
  18. ↑ Keszegh, Pach, Pálvölgyi, 2011 , sid. 293-304.
  19. ↑ Verdière, 1991 , sid. 655-669.
  20. ↑ Collins, Stephenson, 2003 , sid. 233-256.
  21. ↑ Mohar, 1993 , sid. 257-263.

Litteratur

Länkar

 Förpackningsuppgifter
Packningscirklar
Ballongpackning
Andra paket
Pussel