원 패킹 정리

원 패킹 정리(Koebe-Andreev-Thurston 정리라고도 함)는 내부가 분리된 평면에서 원 사이의 가능한 접선 관계를 설명한다. 원 패킹은 내부가 분리된 원(일반적으로 모든 리만 표면에서)의 연결된 집합이다. 원 패킹의 교차 그래프는 각 원에 대한 꼭지점과 접선된 각 원 쌍에 대한 가장자리가 있는 그래프다. 원 패킹이 평면에 있는 경우, 또는 동등하게 구체에 있는 경우, 교차 그래프를 코인 그래프라고 부른다. 더 일반적으로 내부 분리 기하학적 객체의 교차 그래프를 접선 그래프 또는 접촉 그래프라고 한다. 코인 그래프는 항상 연결되고 단순하며 평면적이다. 원 패킹 정리에서는 그래프가 코인 그래프가 되기 위한 유일한 요구사항이 다음과 같이 명시되어 있다.

원 패킹 정리: 연결된 모든 단순 평면 그래프 G에 대해 교차 그래프가 G인 평면에는 원 패킹이 있다.

유니크함

최대 평면 그래프 G는 평면성을 유지하면서 더 이상 가장자리를 추가할 수 없는 유한 단순 평면 그래프다. 그러한 그래프는 항상 독특한 평면 임베딩이 있는데, 임베딩의 모든 면(외면 포함)은 삼각형이다. 즉, 모든 최대 평면 그래프 G는 구에 동형인 단순 복합체의 1-제곱골격이다. 원 패킹 정리는 교차로 그래프가 G와 이형인 원 여러 원으로 원 패킹의 존재를 보장한다. 다음 정리가 보다 공식적으로 설명하듯이, 모든 최대 평면 그래프는 최대 한 개의 패킹을 가질 수 있다.

코베-안드리프-서스턴 정리: G가 유한 최대 평면 그래프인 경우 접선 그래프가 G에 이형화된 원 패킹은 뫼비우스 변환 및 선 반사에 이르기까지 독특하다.

Thurston은^[1] 이러한 고유성이 모스토우 강직성 정리의 결과라고 관찰한다. 이를 보려면 G를 원 패킹으로 나타내도록 한다. 그러면 원이 채워진 평면을 3차원 쌍곡선 공간에 대한 반공간 모델의 경계로 볼 수 있다. 이 관점에서 각 원은 쌍곡선 공간 내에 있는 평면의 경계로 볼 수 있다. 하나는 포장의 원으로부터 이러한 방식으로 일련의 분리 평면을 정의할 수 있고, 두 번째 분리 평면은 포장에 있는 원들 사이의 각 삼각형 간격을 둘러싸는 원들에 의해 정의된다. 이 두 세트의 평면은 직각으로 만나 쌍곡선 다지기로 볼 수 있는 근본적인 영역을 가진 반사 그룹의 생성자를 형성한다. 모스토우 강성에 의해, 이 영역의 쌍곡선 구조는 쌍곡선 공간의 등계까지 독특하게 결정된다. 반평면 모델의 경계에 있는 유클리드 평면에 대한 그들의 행동 관점에서 볼 때, 이러한 등각선은 뫼비우스 변환으로 해석된다.

또한 최대 원리와 세 개의 서로 접하는 원의 중심을 연결하는 삼각형에서 원의 중심에서 형성되는 각도는 반지름에서 단모톤이 감소하고 다른 두 개의 반지름에서 단모톤이 증가한다는 관찰에 기초하여 동일한 고유성 성질에 대한 보다 기본적인 증거가 있다. 동일한 그래프 G에 대해 두 개의 패킹이 주어질 경우, 반사 및 뫼비우스 변환을 적용하여 이 두 패킹의 외부 원이 서로 일치하고 동일한 반지름을 가질 수 있다. 그런 다음, v를 G의 내부 꼭지점으로 하여 두 패킹의 원들이 가능한 멀리 떨어져 있는 크기를 갖도록 한다. 즉, v를 선택하여 두 패킹에서 원 반지름의₁ r/r₂ 비율을 최대화한다. v를 포함하는 G의 각 삼각형 면에 대해, 첫 번째 패킹에서 v에 대한 원의 중심에 있는 각도가 두 번째 패킹의 각도보다 작거나 같으며, 삼각형을 형성하는 다른 두 원들이 두 패킹에서 동일한 비율의₁ r/r을₂ 가질 때만 동등하게 가능하다. 그러나 삼각형의 중심을 둘러싸고 있는 이 모든 삼각형의 각도의 합은 두 패킹에서 모두 2㎛여야 하므로, v에 대한 모든 인접 정점 대 v의 비율이 같아야 한다. 이러한 다른 원들에 차례로 동일한 주장을 적용함으로써, 두 패킹의 모든 원들이 동일한 비율을 갖는다는 것을 따른다. 그러나 외부 원은 비율 1을 갖도록 변형되어 r₁/r₂ = 1과 두 패킹은 모든 원들에 대해 동일한 반지름을 가진다.

정합 지도 이론과의 관계

평면 또는 고차원 공간에서 두 개의 열린 세트 사이의 등각 지도는 두 곡선 사이의 각도를 보존하는 한 세트에서 다른 세트까지의 연속 함수다. 1851년 베른하르트 리만(Bernhard Riemann)에 의해 공식화된 리만 매핑 정리에는 비행기에 있는 어떤 두 개의 열린 위상학적 디스크에 대해, 한 디스크에서 다른 디스크로 일치된 지도가 있다고 명시되어 있다. 정합성 매핑은 메쉬 생성, 지도 투영 및 기타 영역에서 응용프로그램을 가진다. 그러나 명시적인 방법으로 주어진 두 도메인 사이에 정합성 있는 매핑을 구성하는 것이 항상 쉬운 것은 아니다.^[2]

1985년 Bieberbach 회의에서 William Thurston은 원 패킹이 대략 일치 매핑에 사용될 수 있다고 추측했다. 더 정확히 말하면, Thurston은 임의의 열린 디스크 A에서 원의 내부까지의 정합성 있는 매핑을 찾기 위해 서클 패킹을 사용했다; 한 위상 디스크 A에서 다른 디스크 B로의 매핑은 A에서 원까지의 지도를 B에서 원까지의 지도의 역순으로 구성함으로써 찾을 수 있었다.^[2]

Thurston의 아이디어는 영역 A 내에서 면의 육각 테셀레이션에 일부 작은 반지름 r의 원을 포개어 A의 경계 부근의 좁은 영역을 남겨두고 이 반지름의 원들이 더 이상 들어갈 수 없는 넓이 r의 원형을 만드는 것이었다. 그런 다음, 원들의 교차 그래프에서 최대 평면 그래프 G를 만들고, 패킹의 경계에서 모든 원과 인접한 하나의 추가 꼭지점을 구성한다. 원 패킹 정리에서 이 평면 그래프는 모든 가장자리(경계 꼭지점에 입사하는 가장자리 포함)가 원의 접선으로 표시되는 원 패킹 C로 나타낼 수 있다. A의 포장에서 나오는 원은 A의 경계에 해당하는 C의 경계 원을 제외하고 C의 원과 1대 1에 해당한다. 이러한 원의 대응은 뫼비우스 변환에 의해 각각의 원과 세 원 사이의 각 갭이 하나의 패킹에서 다른 패킹으로 매핑되는 A에서 C까지의 연속적인 기능을 구성하는 데 사용될 수 있다. Thurston은 반경 r이 0에 가까워질 때 한계에서 이러한 방식으로 구성된 A에서 C까지의 함수가 리만 매핑 정리에 의해 주어진 정합 함수에 근접할 것이라고 추측했다.^[2]

Thurston의 추측은 Rodin & Sullivan(1987년)에 의해 증명되었다. 보다 정확하게, 그들은 n이 무한대로 갈 때 반지름-1/n 원의 육각형 패킹에서 Thurston의 방법을 사용하여 결정한 함수가_n A의 콤팩트 서브셋에서 A에서 C까지의 정합성 지도로 균일하게 수렴된다는 것을 보여주었다.^[2]

Thurston의 추측의 성공에도 불구하고, 이 방법의 실용적 적용은 컴퓨터 서클 패킹의 어려움과 비교적 느린 융합률로 인해 방해받았다. 그러나 단순하게 연결되지 않은 도메인에 적용하고 폴리곤 도메인의 정합성 매핑을 위한 다른 기술인 슈바르츠-크리스토펠 매핑을 계산하는 수치 기법의 초기 근사치를 선택할 때 몇 가지 장점이 있다.^[2]

교정쇄

원 포장 정리에 대한 많은 알려진 증거들이 있다. 폴 코에베의 원래 증거는 그의 순응적 통일화 정리에 바탕을 두고 있는데, 그것은 미세하게 연결된 평면 영역은 원 영역과 일치하게 동등하다는 것이다. 알려진 몇 가지 다른 위상학적 증거가 있다. Thurston의 증거는 Brouwer의 고정 포인트 정리에 기초한다. 대학원생으로서, 오드 슈람은 프린스턴 대학에서 Thurston의 감독을 받았다. 노데(2011년, 페이지 1628년)가 다시 언급했듯이, 슈람의 논문에 서클 패킹의 존재를 고정 포인트 정리로부터 어떻게 추론할 수 있는가에 대한 '시적 묘사'가 있는데, "무서운 괴물이 순전히 격분하여 팔을 휘두르는 것, 촉수가 서로 비벼대면서 무서운 쉿소리를 내는 것밖에 볼 수 없다"는 것이다. 디리클레 문제에 대한 해결책을 구성하는 페론의 방법의 이산적 변종을 이용한 증거도 있다.^[3] 이브 콜린 드 베르디에르는 특정 구성 공간에서 볼록함수의 최소제로서 서클 패킹의 존재를 증명했다.^[4]

적용들

원 패킹 정리는 평면 기하학, 정합 지도 및 평면 그래프의 다양한 문제를 연구하는 데 유용한 도구다. 원래 립톤과 타르잔에 기인하는 평면 분리막 정리에 대한 우아한 증거를 이렇게 얻어냈다.^[5][6] 원 패킹 정리의 또 다른 적용은 경계도 평면 그래프의 편향되지 않은 한계는 거의 틀림없이 반복된다는 것이다.^[7] 다른 애플리케이션은 커버 타임에 대한 영향을 포함한다.^[8] 경계 그래프에서 가장 큰 고유값에 대한 추정치.^[9]

그래프 도면에서 원 패킹은 각 분해능이^[10] 경계이고 기울기 번호가 경계인 평면 그래프의 도면을 찾는 데 사용되었다.^[11] 곡선 가장자리를 사용하여 평면에서 교차 없이 그릴 수 있는 모든 그래프는 직선 세그먼트 가장자리를 사용하여 교차 없이 그릴 수 있다는 파리의 정리(Fary)는 원의 중심에 정점을 두고 그 사이에 직선 평면 em을 그려서 원 패킹 정리의 단순한 코롤러리로 따른다.침구가 생기다

원 패킹 정리의 더 강한 형태는 모든 다면 그래프와 그 이중 그래프를 두 개의 원 패킹으로 나타낼 수 있다고 주장하는데, 원근 그래프 가장자리를 나타내는 두 개의 접선 원과 같은 가장자리의 이중을 나타내는 두 개의 접선 원은 항상 동일한 관심도에서 서로 직각으로 접선성을 가진다.비행기의 nt 이러한 유형의 패킹은 주어진 그래프를 나타내며 다면체의 모든 가장자리와 접하는 구인 중간 부분이 있는 볼록한 다면체를 구성하는 데 사용될 수 있다. 반대로, 만약 다면체에 중수체가 있다면, 다면체 면과 구의 교차점에 의해 형성된 원과 각 다면체 정점에서 볼 때 구의 지평선에 의해 형성된 원은 이 유형의 이중 패킹을 형성한다.

알고리즘 측면

콜린스 & 스티븐슨(2003)은 윌리엄 서스턴의 아이디어를 바탕으로 서클 패킹을 찾기 위한 숫자적 이완 알고리즘을 설명한다. 그들이 해결하는 원 패킹 문제의 버전은 평면 그래프를 입력하는 것으로서, 모든 내부 면이 삼각형이고 외부 정점이 양수로 라벨이 붙여진 그래프를 사용한다. 그것은 접선이 주어진 그래프를 나타내며 외부 정점을 나타내는 원이 입력에 지정된 반지름을 갖는 원 패킹을 출력한다. 그들이 암시하듯이 문제의 핵심은 우선 포장 안에 있는 원의 반지름을 계산하는 것이다. 일단 반지름이 알려지면 원의 기하학적 위치를 계산하는 것은 어렵지 않다. 유효한 패킹에 해당되지 않는 일련의 임시 반지름으로 시작하여 다음 단계를 반복적으로 수행한다.

1. 입력 그래프의 내부 정점 v를 선택하십시오.
2. 임시 반지름을 사용하여 주변이 서로 접하고 중심 원에 접하는 경우 주변 원들이 원 주위를 감싸는 총 각도 θ을 계산한다.
3. 반경 r의 k 원이 v의 이웃이 주는 것과 동일한 피복각 θ을 주도록 주변 원의 대표적인 반지름 r을 결정한다.
4. v에 대한 새 반지름을 반경 r의 k 원이 정확히 2㎛의 피복 각도를 나타내는 값으로 설정한다.

이러한 각 단계는 단순한 삼각계 계산으로 수행할 수 있으며, 콜린스와 스티븐슨이 주장하는 바와 같이, 모든 피복각들이 정확히 2㎛인 고유한 고정점까지 빠르게 수렴된다. 일단 시스템이 수렴되면, 각각의 연속된 원의 중심을 결정하기 위해 두 개의 인접한 원의 위치와 반지름을 사용하여 각 단계에 원을 한 번에 하나씩 배치할 수 있다.

모하르(1993)는 다면 그래프와 그 이중의 동시 패킹을 찾는 유사한 반복 기법을 설명하고 있는데, 이중 원은 원시 원과 직각이다. 그는 이 방법이 원의 수와 로그 1/4에서 다항식이 소요되며 여기서 ε은 최적의 패킹에서 계산된 패킹의 중심 거리 및 반지름에 대한 바운드가 된다.

일반화

원 패킹 정리는 평면도가 아닌 그래프에 일반화된다. G가 표면 S에 내장될 수 있는 그래프라면 S에는 일정한 곡률 리만 메트릭 d가 있고, G에 접점 그래프가 이형인 원 패킹(S, d)이 있다. S가 닫히고(비교 및 경계가 없는 경우) G가 S의 삼각형이라면, (S, d)과 패킹은 동등성에 부합하도록 고유하다. S가 구체라면 이 등가성은 뫼비우스 변환에 달하고, 토루스라면 등가성은 상수와 등가계로 스케일링에 달하며, S가 적어도 2속(속)을 가지고 있다면 등가성은 등가선까지이다.

원 패킹 정리의 또 다른 일반화에는 인접 정점에 해당하는 원 사이의 지정된 교차각으로 접선 조건을 대체하는 것이 포함된다. 특히 우아한 버전은 다음과 같다. G가 유한 3 연결 평면 그래프(즉, 다면 그래프)라고 가정하면, 그러면 원 패킹 쌍이 있는데, 하나는 교차로 그래프가 G에 이형이고, 다른 하나는 G의 평면 이중과 이형이며, 다른 하나는 교차로 그래프가 G에 이형이며, G에 인접한 모든 정점 및 면에 대해 첫 번째 패킹에 해당하는 원이다. 정점은 얼굴에 해당하는 두 번째 패킹에서 원과 직교하여 교차한다.^[12] 예를 들어, 이 결과를 사면체 그래프에 적용하면 어떤 네 개의 뮤추얼 접선 원에 대해서도 두 번째 세트의 상호 접선 원은 처음 네 개의 원 중 세 개와 직교한다.^[13] 교차로 각도를 반전 거리로 대체하는 추가 일반화를 통해 일부 원이 교차하거나 접히는 것이 아니라 서로 분리되어야 하는 패킹을 지정할 수 있다.^[14]

그러나 또 다른 다양한 일반화는 원이 아닌 모양을 허용한다. G = (V, E)가 유한 평면 그래프이며, G의 각 꼭지점 v에 해당하는 $형상{\displaystyle {}_{}}$ K ${\displaystyle v_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathrm{}}^{}}$ 2 ${\$ 닫힌 단위 디스크와 동형이며 경계가 부드러운 형태라고 가정해 보자. Then there is a packing ${\displaystyle P=(K'_{v}:v\in V)}$ in the plane such that ${\displaystyle K'_{v}\cap K'_{u}\neq \varnothing }$ if and only if ${\displaystyle [v,u]\in E}$ and for each ${\displaystyle v\in V}$ the set ${\displayst$$yle{\displaystyle {}_{}}$ $K'_{v}}$는 K ${\displaystyle v_{}}$ ${\$에서 번역과 스케일링을 통해$$ 얻는다$$.(참고: 원 패킹 정리에서는 꼭지당 3개의 실제 파라미터가 있는데, 이 중 2개는 해당 원의 중심을 설명하고 그 중 1개는 반지름을 기술하고, 1개는 에지당 하나의 방정식이 있다. 이것은 또한 이러한 일반화에도 들어 있다.) 이러한 일반화의 증명 중 하나는 Koebe의 원본 증명과^[15] Brandt와^[16] Harrington의^[17] 정리를 적용하여 얻을 수 있는데, 어떤 미세하게 연결된 영역도 번역과 스케일링까지 경계 구성요소가 특정한 형태를 갖는 평면 영역과 일치하게 동등하다는 것이다.

역사

원 포장 정리는 폴 코에베에 의해 처음 증명되었다.^[15] 윌리엄 서스턴은^[1] 원 패킹 정리를 재발견했고, 그것은 E. M. 안드레이프의 작업에서 따온 것이라고 언급했다. Thurston은 또한 유닛 디스크의 내부에 단순하게 연결된 평면의 적절한 부분집합의 동형성을 얻기 위해 원 패킹 정리를 사용하는 계획을 제안했다. 서클패킹에 대한 Thurston Empression for Circle Packings는 원의 반경이 0이 되는 경향이 있기 때문에 동형성이 리만 지도에 수렴될 것이라는 그의 추측이다. Thurston 추측은 나중에 Burton Rodin과 Dennis Sullivan에 의해 증명되었다.^[18] 이로 인해 서클패킹 정리의 연장, 일치 매핑과의 관계, 적용에 대한 연구가 난무하게 되었다.

참고 항목

• 아폴로니안 개스킷(Apolonian Gasket), 삼각 틈새를 반복적으로 메워 형성된
• 원 패킹, 지정된 접선 없이 원의 밀도 있는 배열
• 도일 나선형, 무한 6-정규격 평면 그래프를 나타내는 원 패킹
• 포드 서클, 합리적인 숫자선을 따라 원을 꾸미는 패킹
• 동그라미가 모두 같은 반지름을 가진 동전 그래프인 페니 그래프
• 고리 보조정리, 패킹에 있는 인접한 원의 크기에 대한 경계

메모들

참조

• Andreev, E. M. (1970), "Convex polyhedra in Lobačevskiĭ spaces", Mat. Sb., New Series, 81 (123): 445–478, MR 0259734.
• Beardon, Alan F.; Stephenson, Kenneth (1990), "The uniformization theorem for circle packings", Indiana Univ. Math. J., 39 (4): 1383–1425, doi:10.1512/iumj.1990.39.39062
• Beardon, Alan F.; Stephenson, Kenneth (1991), "The Schwarz-Pick lemma for circle packings", Illinois J. Math., 35 (4): 577–606, doi:10.1215/ijm/1255987673
• Andreev, E. M. (1970), "Convex polyhedra of finite volume in Lobačevskiĭ space", Mat. Sb., New Series, 83 (125): 256–260, MR 0273510.
• Benjamini, Itai; Schramm, Oded (2001), "Recurrence of distributional limits of finite planar graphs", Electronic Journal of Probability, 6, doi:10.1214/EJP.v6-96, MR 1873300, S2CID 2862151.
• Brandt, M. (1980), "Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete", Bull. De la Soc. Des Sc. Et des Lettr. De Łódź, 30.
• Brightwell, Graham R.; Scheinerman, Edward R. (1993), "Representations of planar graphs", SIAM J. Discrete Math., 6 (2): 214–229, doi:10.1137/0406017.
• Carter, Ithiel; Rodin, Burt (1992), "An inverse problem for circle packing and conformal mapping", Trans. Amer. Math. Soc., 334 (2): 861–875, doi:10.1090/S0002-9947-1992-1081937-X
• Colin de Verdière, Yves (1991), "Une principe variationnel pour les empilements de cercles", Inventiones Mathematicae, 104 (1): 655–669, Bibcode:1991InMat.104..655C, doi:10.1007/BF01245096, S2CID 121028882.
• Collins, Charles R.; Stephenson, Kenneth (2003), "A circle packing algorithm", Computational Geometry. Theory and Applications, 25 (3): 233–256, doi:10.1016/S0925-7721(02)00099-8, MR 1975216.
• Harrington, Andrew N. (1982), "Conformal mappings onto domains with arbitrarily specified boundary shapes", Journal d'Analyse Mathématique, 41 (1): 39–53, doi:10.1007/BF02803393, S2CID 120752035
• Jonnason, Johan; Schramm, Oded (2000), "On the cover time of planar graphs", Electronic Communications in Probability, 5: 85–90.
• Kelner, Jonathan A. (2006), "Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus", SIAM Journal on Computing, 35 (4): 882–902, doi:10.1137/S0097539705447244, hdl:1721.1/30169.
• Keszegh, 벌라주, Pach, 헝가리, Pálvölgyi, Dömötör(2011년),"몇 경사면과 함께 한정적 정도의 평면 그래프 그리는", Brandes, Ulrik에;Cornelsen, 사빈(eds.)Graph도면:18일 국제 심포지엄, GD2010년 콘스탄츠, 독일, 9월 21일부터 24일까지, 2010년에는 선택된 논문, 강의 노트 컴퓨터 과학으로, 6502 vol., 하이델베르크:Springer, 합치하도록 수정되었다.를 대신하여 서명함. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, MR2781274, S2CID 817874.
• Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl., 88: 141–164.
• Lipton, Richard J.; Tarjan, Robert E. (1979), "A separator theorem for planar graphs", SIAM Journal on Applied Mathematics, 36 (2): 177–189, CiteSeerX 10.1.1.104.6528, doi:10.1137/0136016.
• Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.
• Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A. (1997), "Separators for sphere-packings and nearest neighbor graphs", J. ACM, 44 (1): 1–29, doi:10.1145/256292.256294, S2CID 17331739.
• Mohar, Bojan (1993), "A polynomial time circle packing algorithm", Discrete Mathematics, 117 (1–3): 257–263, doi:10.1016/0012-365X(93)90340-Y.
• Rodin, Burton; Sullivan, Dennis (1987), "The convergence of circle packings to the Riemann mapping", Journal of Differential Geometry, 26 (2): 349–360, doi:10.4310/jdg/1214441375.
• Rohde, Steffen (2011), "Oded Schramm: from circle packing to SLE", Ann. Probab., 39 (5): 1621–1667, doi:10.1214/10-AOP590
• Stephenson, Kenneth (1999), "The approximation of conformal structures via circle packing" (PDF), Computational methods and function theory 1997 (Nicosia), Ser. Approx. Decompos., vol. 11, World Sci. Publ., River Edge, NJ, pp. 551–582, MR 1700374.
• Stephenson, Ken (2003), "Circle packing: a mathematical tale" (PDF), Notices Amer. Math. Soc., 50: 1376–1388
• Stephenson, Ken (2005), Introduction to circle packing, the theory of discrete analytic functions, Cambridge: Cambridge University Press.
• Thurston, William (1985), The finite Riemann mapping theorem, Invited talk at the International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture.
• Thurston, William (1978–1981), The geometry and topology of 3-manifolds, Princeton lecture notes.

외부 링크

• CirclePack(그래프에서 서클 패킹을 구성하기 위한 무료 소프트웨어)과 Kenneth Stephenson의 Circle 패킹 참고 문헌 목록