円充填定理

円充填定理^[1]（えんじゅうてんていり、英: circle packing theorem）、サークルパッキング定理^[2]、あるいはケーベ–アンドレエーフ^{[注釈 1]}–サーストンの定理（Koebe–Andreev–Thurston theorem）は、内部に共通部分を持たない複数の円について、それらが外接する条件について述べる定理である。サークルパッキング（英: circle packing）とは、一般にはリーマン面上において、内部に共通部分を持たない（則ち内部が互いに素な）繋げられた円の集まりである。サークルパッキングの交差グラフ（英語版）は、それぞれの円を頂点として持ち、接する円の組を辺とするグラフである。平面上あるいは球面上におけるサークルパッキングの交差グラフは coin graph と呼ばれる。より一般に内部が互いに素な幾何学的対象の交差グラフは tangency graph または contact graph（英語版）と呼ばれる。coin graph は常に連結、単純、平面的なグラフである。円充填定理は円の集合が coin graph になる条件に関する定理である。

任意の有限連結単純平面的グラフ

G

について、交差グラフが

G

と同型なサークルパッキングが存在する。

一意性

極大（maximal）な平面的グラフ $G$ とは、平面的であることを保ちながらそれ以上辺を加えることのできない有限単純平面的グラフである。平面への埋め込み方は一意であり、（外側も含め）すべての面が三角形になる。換言すれば、任意の極大平面的グラフは球に位相同型な複体の1骨格（英語版）である。円充填定理は、有限個の円から成り交差グラフが $G$ に同型なサークルパッキングの存在を保証している。より形式的に言えば、任意の極大な平面的グラフは高々1つのサークルパッキングを持ちうる。

ケーベ–アンドレエーフ–サーストンの定理: 有限極大平面的グラフ $G$ について、メビウス変換と直線による鏡映の違いを除いて、tangency graph が $G$ に同型となるようなサークルパッキングが一意に存在する。

サーストンはこの一意性がモストウの剛性定理から得られることに気づいた。 $G$ をサークルパッキングによって表現することを考える。円が充填された平面を、3次元双曲空間（英語版）の半平面モデルの境界として見ると、それぞれの円は双曲空間内のある平面の境界になる。このようにして、サークルパッキングを成す円から、互いに素な平面の集合を定義することができる。また、サークルパッキングを成す3円に囲まれた三角形型の隙間に外接する円によって定義される平面の集合を考える。この2つの集合に属する平面は互いに垂直に交わり、基本領域（英語版）を双曲多様体として捉えることのできるような鏡映群（英語版）の生成元を形成する。コストウの剛性によって、等長性の違いを除き、この基本領域の双曲構造を一意に決定できる。この際の等長性は、半平面の境界上のユークリッド平面の作用で考えれば、メビウス変換による違いに対応する^[4]。

有限集合に最大元が存在する事を基にした、初等的な一意性の証明も発見されている。互いに接する3つの円の中心をつなげて三角形を作る。三角形の内角は、頂点となる円の半径の増加に応じて減少し、他の2円の半径の増加に応じて増加する。今、グラフ $G$ に2つのサークルパッキング $X 1, X 2$ が存在すると仮定する。サークルパッキングの境界上の頂点において、対応する頂点の $X 1, X 2$ の円がそれぞれ同じ半径を持つように鏡映変換とメビウス変換を施すことができる。 $G$ の頂点 $v$ を、 $X 1, X 2$ の $v$ に対応する円の半径をそれぞれ $r 1, r 2$ として、 $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}r1/r2$ が最大となるようにとる。 $v$ を含む $G$ の三角形型の面について、 $X 1$ における $v$ の頂角 $θ 1$ は、 $X 2$ における $v$ の頂角 $θ 2$ 以下になる。面の他の2頂点における円の比が $r 1 / r 2$ と等しいときは $θ 1 = θ 2$ である。しかし、 $X 1, X 2$ どちらであってもある頂点を取り巻く角は $2 π$ であるから、結果的に $v$ に隣接する頂点における半径比はすべて $r 1 / r 2$ に等しくなる必要がある。同様の議論を隣接する頂点に展開していくと、すべての辺において半径比は $r 1 / r 2$ と等しくなる。境界の点の円について、半径が等しく、つまり $r 1 / r 2 = 1$ となるように変換を施していた。したがってすべての頂点において $X 1, X 2$ の円の半径は等しくなり、 $X 1, X 2$ は同じものと証明される。

この初等的証明は2008年以前に、オデッド・シュラムが英語版Wikipediaに投稿したもので、Rohde 2011 によって美しくてかつ簡潔だと評価されている。

等角写像との関係

特定の領域間では、サークルパッキングを等角写像に近似することができる。左の円は右の円に対応している。

2つの開集合間における等角写像は、任意の曲線部分において角度が保存された連続写像である。1851年にベルンハルト・リーマンによって定式化されたリーマンの写像定理によれば、開円板に位相同型な平面上の2つの対象について、一方をもう一方へ移す等角写像が存在する。等角写像は計算格子や投影法に応用される。しかし、与えられた2つの領域について等角写像を構成する明確な方法は存在しない^[5]。

1985年、ビーベルバッハ会議にて、ウィリアム・サーストンは等角写像を近似するために、サークルパッキングを使うことができると予想した。より正確に言えば、サーストンは、任意の開円板 $A$ からその内部へ変換する等角写像を求めるために、サークルパッキングを用いた。開円板に位相同型な図形 $A, B$ について、 $A$ から $B$ への写像は、 $A$ から円への写像と、 $B$ から円への写像の逆の合成によって求めることができる^[5]。

サーストンのアイデアは、領域 $A$ 内の平面の六角形タイルに半径 $r$ の小さい円を充填して、 $A$ の境界の付近に、これ以上半径 $r$ の円を詰めることのできない幅 $r$ の狭い領域を作るものであった。交差グラフに、サークルパッキングの境界上のすべての円と繋がった頂点を追加して、極大な平面定グラフを構築する。円充填定理の主張により、（新しく頂点を追加した際に出現したものも含め）すべての辺が円の接触を表すようなサークルパッキング $C$ を用いて、この平面的グラフを表現することができる。 $A$ の境界に対応する $C$ の境界の円を除いて、 $A$ のサークルパッキングを成す円は $C$ の円に一対一対応する。この円の対応は、3円の隙間がメビウス変換によって別の隙間に移されるような、 $A$ から $C$ への連続写像を構築するのに使うことができる。サーストンは、 $r$ が極限の場合である0に近づくにつれて、 $A$ から $C$ への円の対応は、リーマンの写像定理によって存在の保証された等角写像に近づいていくことを予想した^[5]。

サーストンの予想はRodin & Sullivan (1987)によって解決された。より正確に表現すれば、 $n$ が極限に近づくと、半径 $1 / n$ の円による六角形充填のサーストンの方法によって定められた関数 $f n$ は、 $A$ のコンパクト補集合上において $A$ から $C$ への等角写像に一様収束することが示された^[5]。

予想の成立は確認されたものの、サークルパッキングは計算が難しく、また収束速度が相対的に遅かったために、この方法を実践することは困難を極めた^[6]。しかし、非単連結な領域に適用するときや、シュワルツ＝クリストッフェル写像（英語版）を計算する際の最初の近似値の決定をする場面などには幾つかの利点がある^[5]。

証明

円充填定理の証明は様々なものが知られている。パウル・ケーベによる最初の証明は、有限連結平面領域は円領域と共形同値であるという定理を基にしている。位相幾何学による証明は複数存在する。サーストンはブラウワーの不動点定理を用いた。オデッド・シュラムは大学院時代にプリンストン大学にてサーストンの指導を受けた。 Rohde (2011, p. 1628) が詳しく述べているように、不動点定理から円充填定理をどのように演繹するかについてのシュラムの論文には、"詩的な供述"がある。

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.

ディリクレ問題の解の構築におけるペロン法（英語版）の変種を用いた方法もある^[7]。イヴ・コリン・ド・ヴェルディエール（英語版、フランス語版）はある配置空間（英語版）上の凸関数を最小値化するものとして、サークルパッキングの存在を証明した^[8]。

応用

円充填定理は、平面的グラフ幾何学や等角写像の様々な問題を研究するための有用な道具である。リプトン（英語版）とタージャンによって最初に証明された^[9]平面グラフ分離定理（英語版）の別証明も円充填定理によって得られている^[10]。頂点の次数が制限された平面的グラフの distributional limit はほとんど確実に再帰的であるという定理にも応用される^[11]。他に種数の制限されたグラフの最大の固有値^[12]や cover time ^[13]への影響などへの応用もある。

グラフ描画（英語版）において、サークルパッキングは角分解能（英語版）^[14]とSlope number（英語版）^[15]に制限のついた平面的グラフを求める際に利用される。曲線の辺を用いて描ける交差の無いすべてのグラフは、交差の無い状態を保ったまま線分の辺で描きかえられることを主張する定理であるFáryの定理（英語版）は円充填定理の単純な系である。円の中心を頂点とし、頂点の間に辺を引くと直線的平面埋め込みが得られる。

多面体とその中接球（英語版）。円充填定理によれば、任意の多面体グラフは中接球を持つ多面体で表現できる。

円充填定理のより強い形式として次の定理が得られる。任意の多面体グラフとその双対グラフは、2つのサークルパッキングで表すことができる。また Primal graph の辺を表す2つの相接円と、その辺の双対を表す2つの相接円は、常に平面上の同一の点で互いに直角に接している。このタイプのサークルパッキングは与えられたグラフを表現し、また中接球（英語版）（多面体のすべての辺に接する球）を持つような凸多面体を構築するのに使うことができる。逆に、多面体が中接球を持つならば、多面体の表面と球との交線が成す円と、多面体の各頂点から見た球面上の地平線から成る円は、このタイプの双対のサークルパッキングを作る。

アルゴリズム的な側面

Collins & Stephenson (2003)は、ウィリアム・サーストンの考えを基に、サークルパッキングを求めるための数値的な緩和法（英語版）について記述した。彼らの解いた円充填問題では、内部のすべての面が三角形で、外部の頂点に正の数をラベリングしてある、平面的グラフを入力とする。出力されるものは、与えられたグラフによって接触が表されるサークルパッキングである。外部の頂点の円の半径は、入力した正の数と等しい。彼らの示唆したように、この問題の鍵は、最初に円の半径を計算することだが、一旦半径が定められれば、幾何学的な円の位置を計算によって求めることは困難ではない。まず、妥当なサークルパッキングには対応しない仮の半径を設定して、次の方法を繰り返す。

入力したグラフの内部の頂点 $v$ を選ぶ。
仮の半径を用いて、 $v$ に隣接する $k$ つの頂点の円が互いに接しており、また $v$ の円にも接している場合の、 $k$ つの円が $v$ の円を囲む角度（英語版）の総和 $θ$ を求める。
半径 $r$ の $k$ 個の円が、 $v$ の隣接円と同様に角 $θ$ で囲まれるように、 $r$ の値を決定する。
$θ = 2 π$ となるように $v$ の円の半径を改める。

これらの操作は三角法の簡単な計算によって実行できる。また、コリンズとスティーヴンソンの主張したように、半径のシステムはすべての $θ$ が $2 π$ となるように急速に一意な不動点に収束する。一度収束してしまえば、各段階で2つの隣接する円の位置と半径を用いて連続的に円を定めていき、円を配置することができる。

Mohar (1993) は多面体グラフとその双対のパッキングを同時に求めるための反復的な技術を開発した。このとき、双対の円は primal circle に対して垂直である。Mohar はこの方法で計算をした場合、その多項式時間は、円の個数と $log 1 / ε$ （ $ε$ は、算出されたパッキングの中心と半径と、最適なパッキングの中心と半径との距離の上界）に依ることを証明した。

一般化

サークルパッキングは有限でないグラフにも適用されうる。特に、端点を1つしか持たずに、無限に平面を三角形へ分割する場合、これはユークリッド平面か双曲平面かの、いずれかでしか起こらない。ユークリッド平面の場合は相似性の違いを除いて、双曲平面の場合は等長性の違いを除いて、サークルパッキングは一意である^[16]。

円充填定理は平面でないグラフにも一般化できる。 $G$ を曲面 $S$ に埋め込むことができるならば、 $S$ 上において一定の曲率リーマン計量 $d$ が存在し、また $G$ に同型な contacts graph を持つ $(S, d)$ におけるサークルパッキングが存在する。 $S$ が閉じていて（コンパクトで境界がなく）、 $S$ を三角形に分割して $G$ を得ることができるならば、 $(S, d)$ とサークルパッキングは共形同値の違いを除いてそれぞれ一意である。 $S$ が球面ならばこの共形同値はメビウス変換、トーラスならば定数倍のスケーリングと等長写像までとなる。 $S$ の種数が少なくとも2以上ならば等長写像までとなる。

円充填定理における接触をある一定の角度で交わる円に換えた一般化もなされている。 $G$ を有限3連結平面的グラフ（多面体グラフ）とすると、 $X 1$ の交差グラフが $G$ と同型で、 $X 2$ の交差グラフが $G$ の双対に同型であり、 $G$ の任意の頂点及びそれに隣接する面について、その頂点に対応する $X 1$ の円が、その面に対応する $X 2$ の円と垂直に交わるような、2つのサークルパッキング $X 1, X 2$ が存在する^[17]。例えば、この結果を四面体のグラフに適用してみると、4つの相接する円について、それぞれそのうち3つに直交するような相異なる4つの相接円が存在している^[18]。更なる一般化に、交わる角を反転距離に置き換えたものがあり、交差しておらず、離れていてもよいようなサークルパッキングが認められる^[19]。

他の一般化に円でないものを充填するものがある。有限平面的グラフ $G = (V, E)$ を定め、 $G$ の頂点 $v$ を図形 $K_{v}\subset \mathbb {R} ^{2}$ に対応させる。ここで $K v$ は閉円板に同型で境界は滑らかであるとする。このとき、平面上に $K'_{v}\cap K'_{u}\neq \varnothing$ を満たすパッキング $P=(K'_{v}:v\in V)$ が存在することと、 $[v,u]\in E$ であるかつ、それぞれの頂点 $v\in V$ であって、 $K v$ のスケーリングと移動によって集合 $K v'$ を得られることとは同値である。もとの円充填定理では、頂点ごとに3つの変数があり、2つが円の中心、1つが半径に費やされることに注意されたい。この一般化の証明の一つはケーベの元の証明^[20]とブラントの定理^[21]、ハリントンの定理（任意の有限連結領域は境界要素が特定の形状をもつ平面領域と、平行移動とスケーリングの違いを除いて共形同値であるという定理）^[22]を用いる。

歴史

円充填の研究は1910年には始まっており、葉序のドイル螺旋（英語版）に関するアルノルト・エミヒ（英語版）の研究に見られる^[23]。円充填定理はパウル・ケーベによって最初に証明された^[20]。ウィリアム・サーストンは円充填定理を再発見し^[4]、E. M. アンドレエーフ（E. M. Andreev）の仕事から導けるものだと述べた。サーストンは円充填定理を用いて、単位円の内部に単純連結真部分集合の位相同型物を得る方法を提案した。 Thurston Conjecture for Circle Packings は、この位相同型は円の半径が0に近づけば、リーマン写像に近づくという予想である。後年にバートン・ロディン（英語版）とデニス・サリヴァンによって解決された^[24]。この功績によって円充填定理の拡張や、等角写像との関係、応用の研究が活発になったと言われる。