サムネイル|5頂点の平面的グラフにおける円充填 円充填定理（えんじゅうてんていり、）、サークルパッキング定理、あるいはケーベ–アンドレエーエフ–サーストンの定理（）は、内部に共通部分を持たない複数の円について、それらが外接する条件について述べる定理である。サークルパッキング（）とは、一般にはリーマン面上において、内部に共通部分を持たない（則ち内部が互いに素な）繋げられた円の集まりである。サークルパッキングのは、それぞれの円を頂点として持ち、接する円の組を辺とするグラフである。平面上あるいは球面上におけるサークルパッキングの交差グラフは coin graph と呼ばれる。より一般に内部が互いに素な幾何学的対象の交差グラフは tangency graph または と呼ばれる。coin graph は常に連結、単純、平面的なグラフである。 円充填定理は円の集合が coin graph になる条件に関する定理である。 任意の有限連結単純平面的グラフについて、交差グラフがと同型なサークルパッキングが存在する。 一意性 極大（）な平面的グラフとは、平面的であることを保ちながらそれ以上辺を加えることのできない有限単純平面的グラフである。平面への埋め込み方は一意であり、（外側も含め）すべての面が三角形になる。換言すれば、任意の極大平面的グラフは球面に位相同型な複体の1である。円充填定理は、有限個の円から成り交差グラフがに同型なサークルパッキングの存在を保証している。より形式的に言えば、任意の極大な平面的グラフはただ1つのサークルパッキングを持ちうる。
ケーベ–アンドレエーエフ–サーストンの定理: 有限極大平面的グラフについて、メビウス変換と直線による鏡映の違いを除いて、tangency graph がに同型となるようなサークルパッキングが一意に存在する。
サーストンはこの一意性がモストウの剛性定理から得られることに気づいた。をサークルパッキングによって表現することを考える。円が充填された平面を、3次元の半平面モデルの境界として見ると、それぞれの円は双曲空間内のある平面の境界になる。このようにして、サークルパッキングを成す円から、互いに素な平面の集合を定義することができる。また、サークルパッキングを成す3円に囲まれた三角形型の隙間に外接する円によって定義される平面の集合を考える。この2つの集合に属する平面は互いに垂直に交わり、を双曲多様体として捉えることのできるようなの生成元を形成する。モストウの剛性によって、等長性の違いを除き、この基本領域の双曲構造を一意に決定できる。この際の等長性は、半平面の境界上のユークリッド平面の作用で考えれば、メビウス変換による違いに対応する, Chap. 13.。
有限集合に最大元が存在する事を基にした、初等的な一意性の証明も発見されている。互いに接する3つの円の中心をつなげて三角形を作る。三角形の内角は、頂点となる円の半径の増加に応じて減少し、他の2円の半径の増加に応じて増加する。今、グラフに2つのサークルパッキングが存在すると仮定する。サークルパッキングの境界上の頂点において、対応する頂点のの円がそれぞれ同じ半径を持つように鏡映変換とメビウス変換を施すことができる。の頂点を、のに対応する円の半径をそれぞれとして、が最大となるようにとる。を含むの三角形型の面について、におけるの頂角は、におけるの頂角以下になる。面の他の2頂点における円の比がと等しいときはである。しかし、どちらであってもある頂点を取り巻く角は であるから、結果的にに隣接する頂点における半径比はすべてに等しくなる必要がある。同様の議論を隣接する頂点に展開していくと、すべての辺において半径比はと等しくなる。境界の点の円について、半径が等しく、つまりとなるように変換を施していた。したがってすべての頂点においての円の半径は等しくなり、は同じものと証明される。
この初等的証明は2008年以前に、オデッド・シュラムが英語版Wikipediaに投稿したもので、 によって美しくてかつ簡潔だと評価されている。 等角写像との関係 右|サムネイル|特定の領域間では、サークルパッキングを等角写像に近似することができる。 左の円は右の円に対応している。 2つの開集合間における等角写像は、任意の曲線部分において角度が保存された連続写像である。1851年にベルンハルト・リーマンによって定式化されたリーマンの写像定理によれば、開円板に位相同型な平面上の2つの対象について、一方をもう一方へ移す等角写像が存在する。等角写像は計算格子や投影法に応用される。しかし、与えられた2つの領域について等角写像を構成する明確な方法は存在しない.。
1985年、ビーベルバッハ会議にて、ウィリアム・サーストンは等角写像を近似するために、サークルパッキングを使うことができると予想した。より正確に言えば、サーストンは、任意の開円板からその内部へ変換する等角写像を求めるために、サークルパッキングを用いた。開円板に位相同型な図形について、からへの写像は、から円への写像と、から円への写像の逆の合成によって求めることができる.。
サーストンのアイデアは、領域内の平面の六角形タイルに半径の小さい円を充填して、の境界の付近に、これ以上半径の円を詰めることのできない幅の狭い領域を作るものであった。交差グラフに、サークルパッキングの境界上のすべての円と繋がった頂点を追加して、極大な平面的グラフを構築する。円充填定理の主張により、（新しく頂点を追加した際に出現したものも含め）すべての辺が円の接触を表すようなサークルパッキング を用いて、この平面的グラフを表現することができる。の境界に対応するの境界の円を除いて、のサークルパッキングを成す円はの円に一対一対応する。 この円の対応は、3円の隙間がメビウス変換によって別の隙間に移されるような、からへの連続写像を構築するのに使うことができる。サーストンは、が極限の場合である0に近づくにつれて、からへの円の対応は、リーマンの写像定理によって存在の保証された等角写像に近づいていくことを予想した.。
サーストンの予想はによって解決された。より正確に表現すれば、が極限に近づくと、半径の円による六角形充填のサーストンの方法によって定められた関数は、のコンパクト補集合上においてからへの等角写像に一様収束することが示された.。
予想の成立は確認されたものの、サークルパッキングは計算が難しく、また収束速度が相対的に遅かったために、この方法を実践することは困難を極めた: "Circle packing certainly cannot compete with the classical numerical methods for speed and accuracy."。しかし、非単連結な領域に適用するときや、を計算する際の最初の近似値の決定をする場面などには幾つかの利点がある.。
証明 円充填定理の証明は様々なものが知られている。パウル・ケーベによる最初の証明は、有限連結平面領域は円領域と共形同値であるという定理を基にしている。位相幾何学による証明は複数存在する。サーストンはブラウワーの不動点定理を用いた。オデッド・シュラムは大学院時代にプリンストン大学にてサーストンの指導を受けた。 が詳しく述べているように、不動点定理から円充填定理をどのように演繹するかについてのシュラムの論文には、"詩的な供述"がある。One can just see the terrible monster swinging its arms in sheer rage, the tentacles causing a frightful hiss, as they rub against each other.ディリクレ問題の解の構築におけるの変種を用いた方法もある; .。はある上の凸関数を最小値化するものとして、サークルパッキングの存在を証明した。
応用 円充填定理は、平面的グラフ幾何学や等角写像の様々な問題を研究するための有用な道具である。とタージャンによって最初に証明された の別証明も円充填定理によって得られている。頂点の次数が制限された平面的グラフの distributional limit はほとんど確実に再帰的であるという定理にも応用される。他に種数の制限されたグラフの最大の固有値や cover time への影響などへの応用もある。
において、サークルパッキングはとに制限のついた平面的グラフを求める際に利用される。曲線の辺を用いて描ける交差の無いすべてのグラフは、交差の無い状態を保ったまま線分の辺で描き換えられることを主張する定理であるファーリの定理は円充填定理の単純な系である。円の中心を頂点とし、頂点の間に辺を引くと直線的平面埋め込みが得られる。 サムネイル|多面体とその。円充填定理によれば、任意の多面体グラフは中接球を持つ多面体で表現できる。 円充填定理のより強い形式として次の定理が得られる。任意の多面体グラフとその双対グラフは、2つのサークルパッキングで表すことができる。また Primal graph の辺を表す2つの相接円と、その辺の双対を表す2つの相接円は、常に平面上の同一の点で互いに直角に接している。このタイプのサークルパッキングは与えられたグラフを表現し、また（多面体のすべての辺に接する球）を持つような凸多面体を構築するのに使うことができる。逆に、多面体が中接球を持つならば、多面体の表面と球との交線が成す円と、多面体の各頂点から見た球面上の地平線から成る円は、このタイプの双対のサークルパッキングを作る。
アルゴリズム的な側面 は、 ウィリアム・サーストンの考えを基に、サークルパッキングを求めるための数値的なについて記述した。彼らの解いた円充填問題では、内部のすべての面が三角形で、外部の頂点に正の数をラベリングしてある、平面的グラフを入力とする。出力されるものは、与えられたグラフによって接触が表されるサークルパッキングである。外部の頂点の円の半径は、入力した正の数と等しい。彼らの示唆したように、この問題の鍵は、最初に円の半径を計算することだが、一旦半径が定められれば、幾何学的な円の位置を計算によって求めることは困難ではない。まず、妥当なサークルパッキングには対応しない仮の半径を設定して、次の方法を繰り返す。
入力したグラフの内部の頂点を選ぶ。 仮の半径を用いて、に隣接するつの頂点の円が互いに接しており、またの円にも接している場合の、つの円がの円をの総和を求める。 半径の個の円が、の隣接円と同様に角で囲まれるように、の値を決定する。 となるようにの円の半径を改める。
これらの操作は三角法の簡単な計算によって実行できる。また、コリンズとスティーヴンソンの主張したように、半径のシステムはすべてのがとなるように急速に一意な不動点に収束する。一度収束してしまえば、各段階で2つの隣接する円の位置と半径を用いて連続的に円を定めていき、円を配置することができる。
は多面体グラフとその双対のパッキングを同時に求めるための反復的な技術を開発した。このとき、双対の円は primal circle に対して垂直である。Mohar はこの方法で計算をした場合、その多項式時間は、円の個数と（は、算出されたパッキングの中心と半径と、最適なパッキングの中心と半径との距離の上界）に依ることを証明した。
一般化 サークルパッキングは有限でないグラフにも適用されうる。特に、端点を1つしか持たずに、無限に平面を三角形へ分割する場合、これはユークリッド平面か双曲平面かの、いずれかでしか起こらない。ユークリッド平面の場合は相似性の違いを除いて、双曲平面の場合は等長性の違いを除いて、サークルパッキングは一意である。
円充填定理は平面でないグラフにも一般化できる。を曲面に埋め込むことができるならば、上において一定の曲率リーマン計量が存在し、またに同型な contacts graph を持つにおけるサークルパッキングが存在する。が閉じていて（コンパクトで境界がなく）、を三角形に分割してを得ることができるならば、とサークルパッキングは共形同値の違いを除いてそれぞれ一意である。が球面ならばこの共形同値はメビウス変換、トーラスならば定数倍のスケーリングと等長写像までとなる。の種数が少なくとも2以上ならば等長写像までとなる。
円充填定理における接触をある一定の角度で交わる円に換えた一般化もなされている。を有限3連結平面的グラフ（多面体グラフ）とすると、の交差グラフがと同型で、の交差グラフがの双対に同型であり、の任意の頂点及びそれに隣接する面について、その頂点に対応するの円が、その面に対応するの円と垂直に交わるような、2つのサークルパッキングが存在する。例えば、この結果を四面体のグラフに適用してみると、4つの相接する円について、それぞれそのうち3つに直交するような相異なる4つの相接円が存在している。更なる一般化に、交わる角を反転距離に置き換えたものがあり、交差しておらず、離れていてもよいようなサークルパッキングが認められる。
他の一般化に円でないものを充填するものがある。有限平面的グラフを定め、の頂点を図形に対応させる。ここでは閉円板に同型で境界は滑らかであるとする。このとき、平面上にを満たすパッキングが存在することと、であるかつ、それぞれの頂点 であって、のスケーリングと移動によって集合を得られることとは同値である。もとの円充填定理では、頂点ごとに3つの変数があり、2つが円の中心、1つが半径に費やされることに注意されたい。この一般化の証明の一つはケーベの元の証明.とブラントの定理、ハリントンの定理（任意の有限連結領域は境界要素が特定の形状をもつ平面領域と、平行移動とスケーリングの違いを除いて共形同値であるという定理）を用いる。
歴史 円充填の研究は1910年には始まっており、葉序のに関するの研究に見られる。円充填定理はパウル・ケーベによって最初に証明された.。ウィリアム・サーストンは円充填定理を再発見し, Chap. 13.、E. M. アンドレエーエフ（E. M. Andreev）の仕事から導けるものだと述べた。サーストンは円充填定理を用いて、単位円の内部に単純連結真部分集合の位相同型物を得る方法を提案した。 Thurston Conjecture for Circle Packings は、この位相同型は円の半径が0に近づけば、リーマン写像に近づくという予想である。後年にとデニス・サリヴァンによって解決された。この功績によって円充填定理の拡張や、等角写像との関係、応用の研究が活発になったと言われる。
脚注
注釈
出典
参考文献
関連項目
アポロニウスのギャスケット、三角形の隙間を無限個の円によって反復的に充填した図形。 、接触を特定することなく配置された円。 、6-正則平面的グラフを表す無限個の円によるパッキング。 フォードの円、有理数直線に詰め込まれた円の集合。 、半径の等しい coin graph。 、円充填において、隣接円の大きさの限界を与える補題。
外部リンク
CirclePack （グラフからサークルパッキングを構築するフリーソフトウェア） Circle packing bibliography by Kenneth Stephenson, Univ. of Tennessee