Cirkelpakningssætning

Cirkelpakningssætningen (også kendt som Koebe-Andreev-Thurston-sætningen ) beskriver, hvordan cirkler kan røres, hvis de ikke har fælles indre punkter. En skæringsgraf (nogle gange kaldet en tangency graph ) af en pakning af cirkler er en graf, hvis toppunkter svarer til cirkler, og hvis kanter svarer til tangency points. Hvis cirklerne er pakket på et plan (eller tilsvarende på en kugle), kaldes deres skæringsgraf en møntgraf . Møntgrafer er altid forbundet, enkle og plane . Cirkelpakningssætningen siger, at det omvendte også er sandt:

Cirkelpakningssætning : For enhver forbundet simpel plan graf G , er der en cirkelpakning i planet, hvis skæringsgraf er isomorf med G.

Unikhed

En graf G kaldes trianguleret plan (eller maksimal plan), hvis den er plan, og enhver forbundet komponent af komplementet af indlejringen af ​​G i en kugle har nøjagtig tre kanter på grænsen, eller med andre ord, hvis G er en en -dimensionelt spændende træ af et simpelt kompleks , der er homøomorft til en kugle. Enhver trianguleret plan graf G er forbundet og enkel, så cirkelpakningssætningen garanterer eksistensen af ​​en pakning, hvis tangensgraf er isomorf med G . Sådan en graf G skal være endelig, så den tilsvarende pakning får et endeligt antal cirkler. Som den følgende sætning siger, kan enhver maksimal plan graf højst svare til én pakning.

Koebe-Andreev-Thurston-sætning : Hvis G er en finit trianguleret plan graf, så er en cirkelpakning, hvis tangensgraf er (isomorf med) G , unik op til Möbius-transformationer og refleksioner med hensyn til linjer.

Thurston [1] bemærkede, at denne unikhed er en konsekvens af Mostows rigiditetssætning . Planet, som cirklerne er pakket i, kan ses som grænsen for Poincaré-modellen i et halvt rum . Fra dette synspunkt er enhver cirkel grænsen for et plan i det hyperbolske rum. Hver pakning af cirkler kan associeres med et sæt af ikke-skærende planer, såvel som et andet sæt af ikke-skærende planer defineret af trekantede områder mellem de tre pakningscirkler. Planer fra forskellige sæt skærer hinanden i rette vinkler og svarer til generatorerne af refleksionsgruppen , hvis fundamentale domæne kan betragtes som en hyperbolsk manifold . Ved Mostows rigiditetssætning er den hyperbolske struktur af dette domæne unikt defineret op til isometrier af det hyperbolske rum. Disse isometrier bliver, når de betragtes som handling på grænsen af ​​Poincaré-modellen, til Möbius-transformationer.

Der er også et elementært bevis baseret på maksimumsprincippet og på den iagttagelse, at i en trekant, der forbinder centrene i tre gensidigt tangerende cirkler, aftager vinklen dannet ved toppunktet i midten af ​​en af ​​cirklerne monotont, når dens radius øges og øges monotont, da nogen af ​​de to andre cirkler øges. Givet to pakninger for den samme graf G , kan refleksioner og Möbius-transformationer bruges til at få de ydre cirkler i de to pakninger til at svare til hinanden og have samme radier. Lad derefter v  være et indre toppunkt af G , hvor de to-pakkede cirkler har størrelser så langt fra hinanden som muligt. Det vil sige, v er valgt for at maksimere forholdet r 1 / r 2 af radierne af cirklerne i de to pakker. Det følger heraf, at for hver trekantet flade af G , der indeholder v , er vinklen med toppunktet for centrum af cirklen svarende til v i den første pakning mindre end eller lig med vinklen i den anden pakning, med kun lighed, hvis de to andre cirkler danner en trekant med det samme forhold r 1 / r 2 radier af den anden pakning. Men summen af ​​vinklerne for alle trekanter, der omgiver trekantens centrum, skal være 2π i begge pakninger, så alle hjørner, der støder op til v , skal have samme forhold som v selv . Ved at anvende samme ræsonnement på andre cirkler viser det sig, at alle cirklerne i begge pakker har samme relation. Men de ydre cirkler transformeres til at have et forhold på 1, så r 1 / r 2 = 1 og begge pakker har lige store radier for alle cirkler.

Generaliseringer af cirkelpakningssætningen

Cirkelpakning kan generaliseres til grafer, der ikke er plane.

Hvis G er en graf, der kan indlejres i en orienterbar overflade S , så eksisterer der en Riemannsk metrisk d med konstant krumning på S og en cirkel, der pakker sig ind i ( S , d ), hvis tangensgraf er isomorf med G. Hvis S er lukket ( kompakt og har ingen grænse ) og G  er en triangulering af S , så er ( S , d ) og pakning unikke op til konform ækvivalens. Hvis S  er en sfære, så er en konform ækvivalens en ækvivalens op til Möbius-transformationer; hvis det er en torus, så op til multiplikation med en konstant og isometrier; hvis overfladens slægt er mindst 2, op til isometri.

En anden generalisering af cirkelpakningssætningen involverer at erstatte tangensbetingelsen ved at specificere skæringsvinklen mellem cirkler svarende til nabospidser. Især er der følgende elegante version af denne teorem. Antag , at G er en endelig 3-forbundet plan graf (med andre ord en polyedrisk graf ), så er der et par cirkelpakninger, således at skæringsgrafen for den ene pakning er isomorf med G , og skæringsgrafen for den anden er isomorf til G 's plane dobbeltgraf . Desuden skærer cirklen svarende til toppunktet i den første pakning i en ret vinkel med cirklen svarende til ansigtet i den anden pakning for et hvilket som helst toppunkt i G og en flade der støder op til den [2] . For eksempel, at anvende dette resultat på en graf af et tetraeder giver, for alle fire parvise tangentcirkler, et andet sæt af fire gensidigt tangentielle cirkler, som hver er ortogonale i forhold til tre af det første sæt [3] . En yderligere generalisering kan opnås ved at erstatte skæringsvinklen med en omvendt afstand [4] .

En anden generalisering tillader brugen af ​​andre former end cirkler. Antag, at G = ( V , E ) er en finit plan graf, og hvert toppunkt v i G svarer til en figur , der er homøomorf til den lukkede enhedsskive, og hvis grænse er glat. Så er der en pakning på flyet sådan, at hvis og kun hvis og for hver sættet er opnået fra ved at flytte og skalere. (Bemærk, at den oprindelige cirkelpakningssætning har tre toppunktsparametre, hvoraf to angiver midten af ​​den tilsvarende cirkel og én angiver radius, og der er én ligning for hver kant. Dette gælder også for denne generalisering.) Et bevis på denne generalisering opnås ved at bruge det originale bevis fra Koebe [5] og sætningen fra Brandt [6] og Harrington [7] , der siger, at ethvert endeligt forbundet domæne er konformt ækvivalent med et fladt domæne, hvis komponentgrænser har specifikke former op til oversættelse og skalering.

Forholdet til teorien om konforme kortlægninger

En konform kortlægning mellem to åbne delmængder af et højere dimensionelt plan eller rum er kontinuerlig og bevarer vinklerne mellem to kurver. Riemanns kortlægningssætning , formuleret af Riemann i 1851, siger, at der for to åbne topologiske diske i planet eksisterer en konform kortlægning fra den ene disk til den anden.

Konforme kortlægninger har applikationer til konstruktion af beregningsgitter , kortprojektioner og andre områder. Det er dog ikke altid let at konstruere en konform kortlægning mellem to givne regioner eksplicit [8] .

På en konference i 1985 foreslog William Thurston , at cirkelpakning kunne bruges til at tilnærme konforme kortlægninger. Mere præcist brugte Thurston cirkelpakninger til at finde en konform kortlægning af en vilkårlig åben (topologisk) skive A ind i det indre af en cirkel. En afbildning fra en topologisk skive til en anden skive B kan derefter findes ved at overlejre en afbildning fra A til en cirkel og en afbildning omvendt til afbildningen af ​​B til en cirkel [9] .

Thurstons idé var at konstruere en pakning af cirkler med en lille radius r i form af en sekskantet flisebelægning [10] på planet inde i området A , hvilket efterlader en smal strimmel nær grænsen til A , hvori en cirkel mere med denne radius kan ikke placeres. Derefter konstrueres den maksimale plane graf G ud fra cirkelskæringsgrafen , og et ekstra toppunkt tilføjes ved siden af ​​alle cirkler på pakningsgrænsen. Ved cirkelpakningssætningen kan denne plane graf repræsenteres af en cirkelpakning C , hvor alle kanter (inklusive kanter, der falder ind mod grænsespidser) er repræsenteret ved cirklernes tangens. Cirklerne fra pakningen A svarer en-til-en til cirklerne fra C , bortset fra grænsecirklen C , som svarer til grænsen for A. Denne korrespondance kan bruges til at konstruere en kontinuerlig kortlægning fra A til C , hvor hver cirkel og hvert mellemrum mellem tre cirkler kortlægges fra en pakning til en anden ved hjælp af en Möbius-transformation . Thurston foreslog, at da radius r har en tendens til nul, tenderer afbildningen fra A til C , konstrueret på denne måde, til en konform funktion, som er givet af Riemanns sætning [9] .

Thurstons formodning blev bevist af Rodin og Sullivan [11] . Mere præcist viste de, at da n har en tendens til det uendelige, konvergerer funktionen f n opnået ved Thurstons metode ensartet på kompakte delmængder A fra en pakning med cirkler med radius 1/ n til en konform afbildning fra A til C [9] .

På trods af bekræftelsen af ​​Thurstons formodning, er den praktiske anvendelse af denne metode hæmmet af kompleksiteten i at konstruere cirkelpakninger og den relativt langsomme konvergens. Denne metode kan dog med succes bruges i tilfælde af ikke- simpelt forbundne domæner og i valget af indledende tilnærmelser til numeriske metoder, der beregner Schwartz-Christoffel-kortlægninger  - en noget anderledes metode til at konstruere konforme afbildninger af polygonale domæner [9] .

Anvendelser af cirkelpakningssætningen

Cirkelpakningssætningen er et nyttigt værktøj til at studere forskellige problemer inden for planimetri, konforme afbildninger og plane grafer. Et elegant bevis for den plane grafopdelingssætning , oprindeligt bevist af Lipton og Tarjan [12] , opnås ved hjælp af cirkelpakningssætningen [13] . En anden anvendelse af cirkelpakningssætningen er at bevise påstanden om, at de uvildige grænser for plane grafer med afgrænset grad næsten altid er rekursive [14] .

Andre anvendelser er afledninger for tidspunktet for tilfældig gennemgang af en graf [15] og estimering af den maksimale egenværdi af grafer af afgrænset slægt [16] .

Ved grafvisualisering bruges cirkelpakning til at finde en repræsentation af en plan graf med begrænset opløsning [17] og med et begrænset antal hældninger [18] .

Bevis for sætningen

Der er mange velkendte beviser for cirkelpakningssætningen. Paul Koebes originale bevis er baseret på hans konforme parametriseringssætning, der siger, at et endeligt forbundet domæne er konformt ækvivalent med en cirkel. Der er flere forskellige kendte topologiske beviser. Thurstons bevis er baseret på Brouwers fikspunktssætning .

Der er også et bevis ved hjælp af en diskret version af Perron-metoden til at konstruere en løsning på Dirichlet-problemet . Yves Colin de Verdière beviste [19] eksistensen af ​​en cirkelpakning som en minimering af en konveks funktion på nogle konfigurationsrum.

Konsekvenser

Farees sætning , som siger, at enhver graf, der kan repræsenteres uden skæringspunkter i planet ved hjælp af buede kanter, også kan tegnes uden skæringspunkter ved hjælp af linjestykker, er en simpel konsekvens af cirkelpakningssætningen - at placere toppunkterne i cirklernes centrum og tegning af linjesegmenter, der forbinder de rørende cirkler, får vi en repræsentation med kanter i form af segmenter.

En streng version af pakningssætningen siger, at enhver polyedrisk graf og dens dobbelte graf kan repræsenteres af to pakninger af cirkler, således at de to tangentcirkler repræsenterer en kant af basisgrafen, og de to andre tangentcirkler repræsenterer en kant af den duale grafen skærer hinanden i rette vinkler. Denne type pakning kan bruges til at konstruere et konveks polyeder , der er repræsenteret af en given graf og har en semi-indskrevet kugle , en kugle, der tangerer alle kanter af polyhedron . Omvendt, hvis et polyeder har en semi-indskrevet kugle, dannes cirklerne dannet af kuglens skæring med polyederens flader og cirklerne dannet af kuglens horisonter, som er synlige fra polyederens hjørner. dobbeltpakninger.

Algoritmiske aspekter

Collins og Stephenson [20] beskrev en numerisk afslapningsalgoritme til at finde cirkelpakninger baseret på ideerne fra William Thurston . Den version af cirkelpakningsproblemet, de løser, tager som input en plan graf, hvor alle indvendige flader er trekanter, og alle ydre hjørner er mærket med positive tal. Algoritmen giver en pakning af cirkler, hvis tangentpunkter repræsenterer den givne graf, og for hvilke cirklerne, der repræsenterer de ydre hjørner, har den radius, der er angivet i inputtet. Som de foreslog, ligger nøglen til problemet i den indledende beregning af radierne af pakningscirklerne. Hvis radierne er kendt, er de geometriske positioner af cirklerne ikke svære at beregne. De starter med prøveradier, der ikke matcher rigtige pakker, og går derefter igennem følgende trin:

  1. Lad os vælge et internt toppunkt for inputgrafen, dette toppunkt svarer til en cirkel, som vi vil betegne v . Naboende hjørner svarer til lober , dvs. cirkler, der tangerer den valgte cirkel. Lad k  være antallet af kronblade.
  2. Beregn den samlede vinkel θ, der overlappes af k nabocirkler omkring cirklen v , hvis de er placeret tæt på hinanden, og som berører den centrale cirkel.
  3. Beregn den gennemsnitlige radius r s for kronbladene, således at k cirkler med radius r s overlapper den samme vinkel θ givet af naboerne v .
  4. Indstil en ny radius r n for v , således at k cirkler med gennemsnitsradius ville overlappe nøjagtigt 2π.

Hvert af disse trin kan udføres med simple trigonometriske beregninger, og som Collins og Stephenson har påpeget, konvergerer systemet af radier til et enkelt fikspunkt, for hvilket alle dækkende vinkler er 2π. Når systemet af radier er konvergeret, kan cirklerne placeres en ad gangen, ved hvert trin ved at bruge positionen og radierne af de to tilstødende cirkler til at beregne midten af ​​hver vellykket cirkel.

Mohar [21] beskriver en lignende iterativ teknik til at finde pakninger af en polyedrisk graf og dens dual, hvor de dobbelte cyklusser skærer hinanden vinkelret med de underliggende cirkler. Han beviste, at metoden virker i polynomiel tid i antallet af cirkler og i log 1/ε, hvor ε er grænsen for afstande fra centrene og forskellen mellem radierne af den beregnede pakning og den optimale pakning.

Historie

Cirkelpakningssætningen blev først bevist af Paul Koebe [5] .

William Thurston [1] genopdagede cirkelpakningssætningen og bemærkede, at den følger af E. M. Andreevs arbejde. Thurston foreslog også et skema til at bruge cirkelpakningssætningen til at opnå en homeomorfisme af et forbundet sæt i planet til det indre af enhedscirklen. Thurstons cirkelpakningsformodning  er antagelsen om, at en homeomorfisme konvergerer til et Riemann-kort , da radierne har en tendens til nul. Thurstons formodning blev senere bevist af Burton Rodin og Dennis Sullivan [11] . Dette har ført til adskillige undersøgelser af generaliseringer af cirkelpakningssætningen, samt undersøgelser af sammenhænge med konforme kortlægninger og anvendelser af sætningen.

Se også

Noter

  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. ↑ Hvis cirklernes centre danner et rektangulært gitter, kaldes pakningen kvadratisk. Hvis cirklernes centre danner et trekantet gitter, kaldes pakningen sekskantet.
  11. ↑ 1 2 Rodin og 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 og 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.

Litteratur

Links

 Emballeringsopgaver
Pakke cirkler
Ballonpakning
Andre pakker
Gåde