Çember sıkıştırma teoremi

küçükresim| Çember sıkıştırma teoremi (Koebe-Andreev-Thurston teoremi olarak da bilinir), düzlemde iç kısımları ayrık olan çemberler arasındaki olası teğetlik ilişkilerini tanımlar. Dairesel sıkıştırma, içleri ayrık olan bağlantılı bir çember koleksiyonudur (genel olarak herhangi bir Riemann yüzeyinde). Bir çember sıkıştırmasının kesişme çizgesi (grafı), her çember için bir tepe noktasına ve teğet olan her çember çifti için bir kenara sahip olan çizgedir. Çember sıkıştırma, düzlemde veya eşdeğer olarak küre üzerindeyse, kesişme çizgesine madeni para (coin) çizgesi denir; daha genel olarak, iç-ayrık geometrik nesnelerin kesişme çizgelerine, teğetlik çizgeleri veya temas çizgeleri denir. Madeni para çizgeleri her zaman bağlı, basit ve düzlemseldir. Çember sıkıştırma teoremi, bunların bir çizgenin madeni para çizgesi olması için tek gereklilik olduğunu belirtir: Çember sıkıştırma teoremi: Bağlı her basit düzlemsel G çizgesi için, düzlemde kesişme çizgesinin G (ile eşbiçimli -izomorfik-) olan bir çember sıkıştırması vardır. == Benzersizlik == Bir maksimal düzlemsel çizge G, düzlemselliği korurken daha fazla kenarın eklenemeyeceği sonlu basit bir düzlemsel çizgedir. Böyle bir çizgenin, gömme işleminin her yüzünün (dış yüz dahil) bir üçgen olduğu her zaman benzersiz bir düzlemsel gömmesi vardır. Diğer bir deyişle, her bir maksimal düzlemsel çizge G, küreye homeomorfik olan basit bir kompleksin 1-iskeletidir. Çember sıkıştırma teoremi, kesişme çizgesi G'ye izomorfik olan sonlu sayıda çember ile sıkıştırılmış bir çemberin varlığını garanti eder. Aşağıdaki teoremin daha formal olarak belirttiği gibi, her maksimal düzlemsel çizge en fazla bir sıkıştırmaya sahip olabilir. Koebe–Andreev–Thurston teoremi: G sonlu bir maksimal düzlemsel çizge ise, teğet çizgesi G’ye izomorfik olan çember sıkıştırması, Möbius dönüşümlerine ve doğrulardaki yansımalara kadar benzersizdir. Thurston, Chap. 13., bu benzersizliğin Mostow rijitlik teoreminin bir sonucu olduğunu gözlemler. Bunu görmek için, G bir çember sıkıştırmasıyla temsil edilsin. Daha sonra çemberlerin sıkıştırıldığı düzlem, üç boyutlu hiperbolik uzay için bir yarı uzay modelinin sınırı olarak görülebilir; bu bakış açısıyla, her çember hiperbolik uzay içindeki bir düzlemin sınırıdır. Bu şekilde sıkıştırmanın çemberlerinden bir dizi ayrık düzlem ve sıkıştırma içindeki üç çemberin arasındaki her bir üçgen boşluğu çevreleyen çemberlerle tanımlanan ikinci bir ayrık düzlemler kümesi tanımlanabilir. Bu iki düzlem kümesinin dik açılarla kesişir ve temel alanı hiperbolik bir manifold olarak görülebilen bir yansıma grubunun jeneratörlerini oluşturur. Mostow rijitliği ile, bu alanın hiperbolik yapısı, hiperbolik uzayın izometrisine kadar benzersiz bir şekilde belirlenir; bu izometriler, yarı düzlem modelin sınırındaki Öklid düzlemindeki eylemleri açısından bakıldığında, Möbius dönüşümlerine çevrilir. Maksimum prensibine ve üç karşılıklı teğet çemberin merkezlerini birbirine bağlayan üçgende, çemberlerden birinin merkezinde oluşan açı, yarıçapında azalan monoton, diğer iki yarıçapta artan monotondur ve aynı benzersizlik özelliğinin daha basit bir kanıtı da vardır. Aynı G çizgesi için iki sıkıştırma verildiğinde, bu iki sıkıştırmadaki dış çemberlerin birbirine karşılık gelmesi ve aynı yarıçaplara sahip olması için yansımalar ve Möbius dönüşümleri uygulanabilir. O halde v, iki sıkıştırmadaki çemberlerin olabildiğince birbirinden uzak boyutlara sahip olduğu bir G iç tepe noktası olsun: bu, v’nin iki sıkıştırmadaki çemberlerinin yarıçaplarının r1/r2 oranını maksimize etmek için seçilmesi demektir. G’nin v içeren her bir üçgen yüzü için, birinci sıkıştırmadaki v için çemberin merkezindeki açının, ikinci sıkıştırmadaki açıya eşit veya daha küçük olduğu izlenir; eşitlik yalnızca üçgeni oluşturan diğer iki daire iki sıkıştırmada aynı r1/r2 yarıçap oranına sahipken olur. Ancak, üçgenin merkezini çevreleyen tüm bu üçgenlerin açılarının toplamı, her iki sıkıştırmada da 2, olmalıdır, bu nedenle, v’ye komşu tüm köşeler, v’nin kendisiyle aynı orana sahip olmalıdır. Aynı argümanı diğer çemberlere sırayla uygulayarak, her iki sıkıştırmadaki tüm çemberlerin aynı orana sahip olduğu sonucu çıkar. Ancak dış çemberler oran 1 olacak şekilde dönüştürülmüştür, yani r1/r2 = 1 ve iki sıkıştırmada tüm çemberler için aynı yarıçaplara sahiptir. == Açıkorur dönüşüm (conformal mapping) teorisi ile ilişkiler == sağ|küçükresim| Düzlemdeki veya daha yüksek boyutlu bir uzaydaki iki açık küme arasındaki açıkorur dönüşüm, herhangi iki eğri arasındaki açıları koruyan bir kümeden diğerine sürekli bir fonksiyondur. 1851'de Bernhard Riemann tarafından formüle edilen Riemann dönüşüm teoremi, düzlemdeki herhangi iki açık topolojik disk için, bir diskten diğerine uyumlu bir dönüşüm olduğunu belirtir. Açıkorur dönüşümlerin ağ oluşturma, harita projeksiyonu ve diğer alanlarda uygulamaları vardır. Ancak, iki belirli alan arasında açık bir şekilde uyumlu bir dönüşüm oluşturmak her zaman kolay değildir.. 1985'teki Bieberbach konferansında William Thurston, açıkorur dönüşümlere yaklaşmak için çember sıkıştırmaların kullanılabileceğini varsaydı. Daha doğrusu, Thurston, rastgele bir açık disk A’dan bir çemberin içine doğru uyumlu bir dönüşüm bulmak için çember sıkıştırmaları kullandı; bir topolojik disk A’dan başka bir disk B’ye dönüşüm, dönüşümün A’dan bir çembere, dönüşümün tersi ile B’den bir çembere oluşturulmasıyla bulunabilir. Thurston'un fikri, bazı küçük r yarıçaplı çemberleri, A bölgesi içinde, A sınırına yakın dar bir bölge bırakarak, bu yarıçapın daha fazla çemberinin sığamayacağı r genişliğinde, düzlemin altıgen mozaiklemesine yerleştirmekti. Daha sonra, sıkıştırmanın sınırındaki tüm çemberlere bitişik bir ek tepe noktasıyla birlikte, çemberlerin kesişim çizgesinden maksimum düzlemsel bir G çizgesi oluşturur. Çember sıkıştırma teoremi ile, bu düzlemsel çizge, tüm kenarların (sınır tepe noktasına gelenler dahil) çemberlerin teğetleri ile temsil edildiği bir C çember sıkıştırmasıyla temsil edilebilir. A’nın sıkıştırmasındaki çemberler, A’nın sınırına karşılık gelen C’nin sınır çemberi dışında, C'deki çemberlere bire bir karşılık gelir. Çemberlerin bu uyuşması, A’dan C’ye, her çember ve üç çember arasındaki her boşluğun bir sıkıştırmadan diğerine bir Möbius dönüşümü ile eşlendiği sürekli bir fonksiyon oluşturmak için kullanılabilir. Thurston, r yarıçapı sıfıra yaklaştıkça sınırda, bu şekilde inşa edilen A’dan C’ye fonksiyonların Riemann dönüşüm teoremi tarafından verilen açıkorur fonksiyona yaklaşacağını varsaydı. Thurston'un varsayımı tarafından kanıtlanmıştır. Daha kesin olarak, n sonsuza giderken, Thurston'un yöntemi kullanılarak belirlenen fn fonksiyonunun yarıçap-1/n çemberlerin altıgen sıkıştırmalarından A’nın kompakt alt kümeleri üzerinde düzgün bir şekilde A’dan C’ye açıkorur bir dönüşüme yakınsadığını gösterdiler. Thurston varsayımının başarısına rağmen, bu yöntemin pratik uygulamaları, çember sıkıştırmalarının hesaplanmasının zorluğu ve nispeten yavaş yakınsama oranı nedeniyle engellenmiştir. Ancak, basit bir şekilde bağlanmamış alanlara uygulandığında ve çokgen alanların açıkorur dönüşüm için farklı bir teknik olan Schwarz-Christoffel dönüşümlerini hesaplayan sayısal teknikler için ilk yaklaşımları seçerken bazı avantajları vardır. == İspatlar == Çember sıkıştırma teoreminin bilinen birçok kanıtı vardır. Paul Koebe'nin orijinal kanıtı, sonlu bağlanmış bir düzlemsel alanın uygun olarak bir çember alanına eşdeğer olduğunu söyleyen açıkorur tek tipleştirme teoremine dayanmaktadır. Bilinen birkaç farklı topolojik kanıt vardır. Thurston'un kanıtı, Brouwer'in sabit nokta teoremine dayanmaktadır. Yüksek lisans öğrencisi olarak Oded Schramm, Princeton Üniversitesi'nde Thurston tarafından denetlendi. şöyle anlatıyor: Schramm'ın çember paketleme için varoluşun sabit nokta teoreminden nasıl çıkarılabileceğine dair tezinde "şiirsel bir açıklama" var: "Korkunç canavarın saf bir öfke içinde kollarını salladığını, dokunaçların birbirlerine sürtünürken korkunç bir tıslama yarattığını görebiliriz." Ayrıca, Perron'un Dirichlet problemine çözüm üretme yönteminin ayrı bir varyantını kullanan bir kanıt da vardır., Yves Colin de Verdière, belirli bir konfigürasyon uzayında bir dışbükey fonksiyonu en aza indiren çember sıkıştırmanın varlığını kanıtladı. == Uygulamalar == Çember sıkıştırma teoremi, düzlemsel geometri, açıkorur dönüşümler ve düzlemsel çizgelerdeki çeşitli problemleri incelemek için yararlı bir araçtır. İlk olarak Lipton ve Tarjan 'dan kaynaklanan düzlemsel ayırıcı teoreminin zarif bir kanıtı bu şekilde elde edilmiştir. Çember sıkıştırma teoreminin bir başka uygulaması, sınırlı derece düzlemsel çizgelerin tarafsız sınırlarının neredeyse kesin olarak tekrarlanmasıdır. Diğer uygulamalar kapsam süresi için çıkarımlar ve sınırlı-cins çizgelerinin en büyük özdeğeri için tahminler içerir. Çizge çiziminde, sınırlı açısal çözünürlüğe . ve sınırlı eğim sayısına sahip düzlemsel çizgelerin çizimlerini bulmak için çember sıkıştırma kullanılmıştır.. Fáry teoremi, düzlemde kavisli kenarlar kullanılarak kesişme olmaksızın çizilebilen her çizgenin, düz çizgi parçası kenarları kullanılarak kesişmeler olmadan da çizilebileceğini, çember sıkıştırma teoreminin basit bir sonucunu izler: köşeleri çemberlerin merkezlerine yerleştirerek ve aralarında düz kenarlar çizilerek, düz bir düzlemsel gömme elde edilir. küçükresim| Çember sıkıştırma teoreminin daha güçlü bir biçimi, herhangi birçok yüzlü çizgenin ve onun ikili çizgesinin, bir primal çizge kenarını temsil eden iki teğet çemberin ve aynı kenarın çiftini temsil eden iki teğet çemberin her zaman düzlemin aynı noktasında birbirlerine dik açılarda teğetlere sahip olacağı şekilde iki çember sıkıştırması ile temsil edilebileceğini ileri sürer. Bu tip bir sıkıştırma oluşturmak için kullanılabilecek bir dışbükey çok yüzlü, verilen çizgeyi temsil eder ve çok yüzlünün (polyhedron) tüm kenarlarına teğet bir küre olan orta küreye (midsphere) sahiptir. Tersine, birçok yüzlü bir orta küreye sahipse, kürenin çok yüzlü yüzlerle kesişmelerinden oluşan çemberler ve her çok yüzlü tepe noktasından bakıldığında küre üzerinde ufukların oluşturduğu çemberler bu tipte ikili bir sıkıştırma oluşturur. == Algoritmik yönler == , William Thurston'un fikirlerine dayalı olarak, çember sıkıştırmaları bulmak için sayısal bir gevşetme algoritması tanımladılar. Çözdükleri çember sıkıştırma probleminin versiyonu, tüm iç yüzlerin üçgen olduğu ve dış köşelerin pozitif sayılarla etiketlendiği bir düzlemsel çizgeyi girdi olarak alır. Çıktı olarak, teğetleri verilen çizgeyi temsil eden ve bunun için dış köşeleri temsil eden çemberlerin girdide belirtilen yarıçaplara sahip olduğu bir çember sıkıştırması üretir. Önerdikleri gibi, sorunun anahtarı önce sıkıştırmanın içindeki çemberlerin yarıçaplarını hesaplamaktır; Yarıçaplar bilindiğinde, çemberlerin geometrik konumlarının hesaplanması zor değildir. Geçerli bir sıkıştırmaya karşılık gelmeyen bir dizi geçici yarıçapla başlarlar ve ardından aşağıdaki adımları tekrar tekrar gerçekleştirirler: # Giriş çizgesinin dahili bir v tepe noktasını seçin. # Komşular geçici yarıçaplarını kullanarak birbirlerine ve merkez çembere teğet yerleştirilmiş olsaydı, k komşu çemberlerinin v için çemberin etrafını kaplayacağı toplam θ açısını hesaplayın. # Komşu çemberler için temsili bir yarıçap r belirleyin, öyle ki r yarıçaplı k çemberler v'nin komşularının verdiği gibi aynı θ kaplama açısını verecektir. # v için yeni yarıçapı, r yarıçaplı k çemberlerin tam olarak 2'lik bir kaplama açısı vereceği değer olarak ayarlayın. Bu adımların her biri, basit trigonometrik hesaplamalarla gerçekleştirilebilir. Collins ve Stephenson'un iddia ettiği gibi, yarıçaplar sistemi, tüm kaplama açılarının tam olarak 2 olduğu benzersiz bir sabit noktaya hızla yakınsar. Sistem birleştikten sonra, her bir ardışık çemberin merkezini belirlemek için iki komşu çemberin konumları ve yarıçapları kullanılarak her aşamada çemberler birer birer yerleştirilebilir. , çok yüzlü bir çizgenin eşzamanlı sıkıştırmalarını bulmak için benzer bir yinelemeli tekniği ve ikili çemberlerin primal çemberlere dik açılarda olduğu ikiliğini açıklar. Yöntemin, çember sayısında ve log1/ε türünden zaman polinomu aldığını kanıtladı; burada ε, hesaplanan sıkıştırmanın merkezlerinin ve yarıçaplarının optimum sıkıştırmada olanlardan uzaklığına bağlıdır. == Genellemeler == Çember sıkıştırma teoremi, düzlemsel olmayan çizgelere genelleştirir. G, bir yüzeye S gömülebilir bir çizgedir, daha sonra bir sabit olduğu kavisli Riemannsal metrik S ve bir çember sıkıştırması (S, d) kontak çizgesi G'ye izomorfiktir. S kapalıysa (kompakt ve sınırsız) ve G, S'nin üçgenlemesiyse (S, d) ve sıkıştırma, açıkorur eşdeğerliğe kadar benzersizdir. S küre ise, o zaman bu eşdeğerlik Möbius dönüşümlerine bağlıdır; bir simit (torus) ise, S cinsi en az 2 ise, eşdeğerlik bir sabit ve izometrilere göre ölçeklendirmeye kadardır, böylece eşdeğerlik izometrilere kadardır. Çember sıkıştırma teoreminin başka bir genellemesi, teğet koşulunun, komşu köşelere karşılık gelen çemberler arasındaki belirli bir kesişme açısı ile değiştirilmesini içerir. Özellikle zarif bir versiyon aşağıdaki gibidir. G’nin sonlu 3 bağlantılı bir düzlemsel çizge (yani çok yüzlü bir çizge) olduğunu varsayalım, o zaman bir çift çember dolgusu vardır, bunlardan birinin kesişme çizgesi G’ye izomorfiktir, diğeri kesişme çizgesi G’nin düzlemsel çiftine izomorfiktir ve G’deki her tepe noktası ve ona bitişik yüz için, tepe noktasına karşılık gelen birinci sıkıştırmadaki çember, yüze karşılık gelen ikinci sıkıştırmadaki çember ile ortogonal olarak kesişir. Örneğin, bu sonucun dört yüzlü çizgesine uygulanması, herhangi bir dört karşılıklı teğet çember için, her biri ilk dörtten üçüne ortogonal olan dört karşılıklı teğet çemberden oluşan ikinci bir set verir. Kesişme açısını ters mesafe ile değiştiren başka bir genelleme, bazı çemberlerin kesişme veya teğet olmaktan ziyade birbirinden ayrılması gereken sıkıştırmaların spesifikasyonuna izin verir.. Yine başka bir genelleme çeşidi, çember olmayan şekillere izin verir. Farz edin ki G = (V, E) sonlu bir düzlemsel çizgedir ve G’nin her tepe noktası v, kapalı birim diske homeomorfik ve sınırı düzgün olan bir K_v\subset\mathbb R^2 şekline karşılık gelir. Sonra düzlemde bir P = (K'_v:v\in V) sıkıştırması vardır, öyle ki K'_v\cap K'_u e \varnothing ancak ve ancak [v,u]\in E ve her bir v\in V için K'_v kümesi K_v'den çevirerek ve ölçeklendirerek elde edilir. (Orijinal çember sıkıştırma teoreminde, köşe başına üç gerçek parametre vardır, bunlardan ikisi karşılık gelen çemberin merkezini, biri yarıçapı tanımlamaktadır ve kenar başına bir denklem vardır. Bu aynı zamanda bu genellemede de geçerlidir.) Bu genellemenin bir kanıtı, Koebe'nin orijinal ispatı ve Brandt ve Harrington teoreminin uygulanmasıyla elde edilebilir; bu teorem, herhangi bir sonlu bağlanmış alanın, dönüşümlere ve ölçeklemeye kadar sınır bileşenleri belirli şekillere sahip olan bir düzlemsel alana açıkorur eşdeğer olduğunu belirtir. == Tarihçe == Çember sıkıştırma teoremi ilk olarak Paul Koebe tarafından kanıtlandı. William Thurston çember sıkıştırma teoremini yeniden keşfetti ve EM Andreev'in çalışmasından izlediğini belirtti. Thurston ayrıca, düzlemin basitçe bağlanmış uygun bir alt kümesinin birim diskin iç kısmına bir homeomorfizmi elde etmek için daire paketleme teoremini kullanmak için bir şema önerdi. Çember Sıkıştırmaları için Thurston Varsayımı (Thurston Conjecture for Circle Packings), çemberlerin yarıçapları sıfıra yöneldikçe homeomorfizmin Riemann dönüşümüne yakınsayacağı varsayımıdır. Thurston Varsayımı daha sonra Burton Rodin ve Dennis Sullivan tarafından kanıtlandı. Bu, çember sıkıştırma teoreminin uzantıları, açıkorur dönüşümlerle ilişkiler ve uygulamalar hakkında bir araştırma telaşına yol açtı. == Notlar == == Konuyla ilgili yayınlar == * Nachmias Asaf. (2020) The Circle Packing Theorem. In: Planar Maps, Random Walks and Circle Packing. Lecture Notes in Mathematics, vol 2243. Springer, Cham. https://doi.org/10.1007/978-3-030-27968-4_3 * Kenneth Stephenson, (2003), Circle Packing: A Mathematical Tale, Makale * Sally Dong, Yin Tat Lee & Kent Quanrud, (2019), Computing Circle Packing Representations of Planar Graphs, https://arxiv.org/abs/1911.00612 * Kevin Pratt, Connor Riley & Donald R. Sheehy, (1998), Exploring Circle Packing Algorithms, Makale == Ayrıca bakınız == * Apollon contası, üçgen boşlukların tekrar tekrar doldurulmasıyla oluşturulan sonsuz bir conta. * Çember sıkıştırma, belirli teğetler olmadan yoğun çember düzenlemeleri * Doyle spiralleri, sonsuz 6 düzenli düzlemsel çizgeleri temsil eden çember sıkıştırmaları * Ford çemberleri, rasyonel sayı doğrusu boyunca çemberler yığını * Penny çizgesi, dairelerinin tümü eşit yarıçaplara sahip olan madeni para çizgeleri * Halka lemması, bir ambalajdaki bitişik çemberlerin boyutlarına bağlı == Dış bağlantılar == * CirclePack (çizgelerden çember sıkıştırmaları oluşturmak için ücretsiz yazılım) ve Circle packing bibliography Kenneth Stephenson, Tennessee Üniversitesi == Kaynakça == *. * * *. *. *. *. * *. *. * *. *. *. *. *. *. *. *. *. * *. * *. *. *. Kategori:Öklid geometrisi teoremleri