円充填定理

円充填定理（ケーベ・アンドレーエフ・サーストン定理とも呼ばれる）は、平面内で内部が互いに素である円間の可能な接関係を記述する。円充填とは、内部が互いに素である連結された円の集合（一般には任意のリーマン面上）である。円充填の交差グラフは、各円に頂点を持ち、接するすべての円のペアに辺を持つグラフである。円充填が平面上、または球面上にある場合、その交差グラフはコイン グラフと呼ばれる。より一般的には、内部が互いに素な幾何学的オブジェクトの交差グラフは、接グラフまたは接触グラフと呼ばれる。コイン グラフは常に連結され、単純で、平面的である。円充填定理によれば、グラフがコイン グラフであるための要件は次の 2 つだけである。

円充填定理: すべての有限連結単純平面グラフGに対して、その交差グラフがG （と同型）である平面上の円充填が存在する。

極大平面グラフ Gは、平面性を維持しながらそれ以上の辺を追加することができない有限の単純な平面グラフです。このようなグラフには常に一意の平面埋め込みがあり、埋め込みのすべての面 (外面を含む) は三角形です。言い換えると、すべての極大平面グラフGは、球面に同相な単体複合体の 1 スケルトンです。円充填定理は、交差グラフがGに同型である有限個の円による円充填の存在を保証します。次の定理がより正式に述べているように、すべての極大平面グラフには最大で 1 つの充填があります。

Koebe–Andreev–Thurston の定理: G が有限最大平面グラフである場合、接グラフがGと同型である円充填は、メビウス変換と直線の反射 を除いて一意です。

サーストンは、この一意性はモストウの剛性定理の結果であると指摘している。これを理解するために、G を円の詰め込みで表すとしよう。すると、円が詰め込まれた平面は、3 次元双曲空間の半空間モデルの境界とみなすことができる。この見方では、各円は双曲空間内の平面の境界である。このようにして、詰め込みの円から互いに素な平面の集合を定義でき、さらに、詰め込み内の 3 つの円の間の各三角形の隙間を外接する円によって定義される、互いに素な平面の 2 番目の集合を定義できる。これらの 2 組の平面は直角に交わり、反射群の生成元を形成し、その基本領域は双曲多様体とみなせる。モストウの剛性により、この領域の双曲構造は、双曲空間の等長変換を除いて一意に決定される。これらの等長変換は、半平面モデルの境界上のユークリッド平面上での作用の観点から見ると、メビウス変換に変換されます。^[1]

同じ一意性の特性には、より基本的な証明もあります。これは、任意の有限集合に最大値が存在することと、互いに接する 3 つの円の中心を結ぶ三角形において、円の 1 つの中心で形成される角度がその半径に対して単調減少し、他の 2 つの半径に対して単調増加するという観察に基づいています。同じグラフ の 2 つのパッキングが与えられた場合、反射とメビウス変換を適用して、これら 2 つのパッキングの外側の円が互いに対応し、同じ半径を持つようにすることができます。次に、の内部頂点を とし、2 つのパッキングの円のサイズが可能な限り離れるようにします。つまり、 2 つのパッキングの円の半径の比が最大になるように選択します。を含むの各三角形面について、最初のパッキングにおける の円の中心の角度は、2 番目のパッキングにおける角度以下になります。この等式は、三角形を形成する他の 2 つの円が2 つのパッキングで同じ半径比を持つ場合にのみ可能です。しかし、三角形の中心を囲むこれらのすべての三角形の角度の合計は、両方のパッキングにある必要があるため、 から のすべての隣接頂点は、それ自体と同じ比率を持つ必要があります。同じ議論をこれらの他の円に順番に適用すると、両方のパッキングのすべての円が同じ比率を持つことになります。しかし、外側の円は比率 1 になるように変換されているため、と 2 つのパッキングはすべての円に対して同一の半径を持ちます。 ${\displaystyle G}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle r_{1}/r_{2}}$${\displaystyle G}$${\displaystyle v}$${\displaystyle v}$${\displaystyle r_{1}/r_{2}}$${\displaystyle 2\pi }$${\displaystyle v}$${\displaystyle v}$${\displaystyle r_{1}/r_{2}=1}$

平面または高次元空間内の2つの開集合間の等角写像は、2つの曲線間の角度を保存する、一方の集合から他方の集合への連続関数である。1851年にベルンハルト・リーマンによって定式化されたリーマン写像定理は、平面上の任意の2つの位相開円板に対して、一方の円板から他方の円板への等角写像が存在することを述べている。等角写像は、メッシュ生成、地図投影、およびその他の分野で応用されている。しかし、2つの与えられた領域間の等角写像を明示的に構築することは必ずしも容易ではない。^[2]

1985 年のビーバーバッハ会議で、ウィリアム・サーストンは、円充填法を使って等角写像を近似できると推測しました。より正確には、サーストンは円充填法を使って任意の開円板Aから円の内部への等角写像を見つけました。位相円板Aから別の円板Bへの写像は、 Aから円への写像とBから円への写像の逆写像を合成することで見つけられました。 ^[2]

サーストンのアイデアは、領域A内の平面の六角形タイル張りに小さな半径rの円を詰め込み、 Aの境界近くに、この半径の円がこれ以上収まらない幅rの狭い領域を残すというものでした。次に、円の交差グラフと、詰め込みの境界にあるすべての円に隣接する 1 つの追加の頂点から、最大平面グラフGを構築します。円詰め定理により、この平面グラフは、すべての辺 (境界頂点に接するものを含む) が円の接線によって表される円詰めCで表すことができます。 Aの詰め込みからの円は、 Cの円と 1 対 1 で対応しますが、 Cの境界円はAの境界に対応します。この円の対応を使用して、 AからCへの連続関数を構築できます。この関数では、各円と 3 つの円間の各ギャップが、メビウス変換によって 1 つの詰め込みから他の詰め込みにマッピングされます。サーストンは、半径rがゼロに近づく極限では、このように構築されたAからCまでの関数は、リーマン写像定理によって与えられた共形関数に近づくだろうと予想した。 ^[2]

サーストンの予想はロダンとサリバン（1987）によって証明された。より正確には、彼らはnが無限大に近づくにつれて、サーストンの方法を用いて半径1/ nの円の六角形充填から決定された関数fn_が、 Aのコンパクトな部分集合上でAからCへの等角写像に一様に収束することを示した。^[2]

サーストンの予想は成功したものの、円パッキングの計算が難しく、収束速度が比較的遅いため、この方法の実用化は進んでいない。^[3] しかし、単純連結でない領域に適用する場合や、多角形領域の等角写像のための別の手法であるシュワルツ・クリストッフェル写像を計算する数値手法の初期近似値を選択する場合には、いくつかの利点がある。^[2]

円充填定理の証明は数多く知られている。ポール・ケーベの元々の証明は、有限連結平面領域は円領域と共形的に同等であるという彼の共形均一化定理に基づいている。位相的な証明にはいくつかの異なるものが知られている。サーストンの証明は、ブラウワーの不動点定理に基づいている。大学院生として、オデッド・シュラムはプリンストン大学でサーストンの指導を受けた。ローデ (2011, p. 1628) が述べているように、シュラムの博士論文には、円充填の存在が不動点定理からどのように演繹されるかについての「詩的な描写」がある。「恐ろしい怪物が怒りに任せて腕を振り回し、触手が互いにこすれ合って恐ろしいシューという音を立てているのが目に浮かぶ。」また、ディリクレ問題の解を構築する ペロンの方法の離散的変形を使った証明もある。^[4]イヴ・コラン・ド・ヴェルディエールは、ある配置空間上の凸関数の最小化として円充填が存在することを証明した。 ^[5]

円充填定理は、平面幾何学、等角写像、平面グラフのさまざまな問題を研究するための便利なツールです。もともと Lipton と Tarjan ^[6]による平面セパレータ定理の別の証明は、この方法で得られました。^[7] 円充填定理の別の応用は、制限された次数の平面グラフの不偏極限がほぼ確実に再帰的であるということです。^[8] 他の応用には、被覆時間への影響があります。< ^{[9]および制限された}種数グラフの 最大固有値の推定値。^[10]

グラフ描画において、円詰めは、角度分解能が制限された平面グラフの描画^[11]と傾き数が制限された平面グラフの描画を見つけるために使用されてきました。^[12] 曲線のエッジを使用して平面上で交差することなく描画できるすべてのグラフは、直線セグメントのエッジを使用して交差することなく描画することもできるというファリーの定理は、円詰め定理の単純な帰結として導かれます。つまり、円の中心に頂点を配置し、それらの間に直線のエッジを描くと、直線の平面埋め込みが得られます。

円充填定理のより強力な形式は、任意の多面体グラフとその双対グラフは2 つの円充填で表すことができ、主グラフ辺を表す 2 つの接円と、同じ辺の双対を表す 2 つの接円は、平面の同じ点で常に互いに直角に接することを主張します。このタイプの充填は、指定されたグラフを表し、多面体のすべての辺に接する球である中球を持つ凸多面体を構築するために使用できます。逆に、多面体に中球がある場合、球と多面体の面の交点によって形成される円と、各多面体頂点から見た球の水平線によって形成される円は、このタイプの双対充填を形成します。

Collins と Stephenson (2003) は、William Thurstonのアイデアに基づいて、円充填を見つけるための数値緩和アルゴリズムについて説明しています。彼らが解く円充填問題のバージョンは、すべての内部面が三角形で外部頂点が正の番号でラベル付けされた平面グラフを入力として受け取ります。出力として、接線が指定されたグラフを表し、外部頂点を表す円が入力で指定された半径を持つ円充填が生成されます。彼らが示唆するように、問題の鍵は、最初に充填内の円の半径を計算することです。半径がわかれば、円の幾何学的位置を計算するのは難しくありません。彼らは、有効な充填に対応しない仮の半径のセットから始めて、次の手順を繰り返し実行します。

1. 入力グラフの内部頂点v を選択します。
2. 隣接するk個の円が、仮の半径を使用して、互いに接し、中心円にも接するように配置された場合に、v の円の周囲に広がる合計角度 θ を計算します。
3. 半径rのk個の円が、 vの隣接円と同じ被覆角 θ を与えるように、隣接する円の代表的な半径r を決定します。
4. vの新しい半径を、半径rのk個の円が正確に 2π の被覆角を与える値に設定します。

これらの各ステップは、簡単な三角法の計算で実行できます。コリンズとスティーブンソンが主張するように、半径のシステムは、すべての被覆角が正確に 2π である唯一の固定点に急速に収束します。システムが収束すると、各ステップで 2 つの隣接する円の位置と半径を使用して、連続する各円の中心を決定し、円を 1 つずつ配置できます。

Mohar (1993) は、多面体グラフとその双対の同時パッキングを見つけるための同様の反復手法について説明しています。この手法では、双対円が主円に対して直角になっています。彼は、この方法が円の数と log 1/ε の多項式で時間がかかることを証明しています。ここで、ε は、計算されたパッキングの中心と半径と、最適パッキングの中心と半径との距離の上限です。

円パッキングの一種は、いくつかの無限グラフに適用される。特に、端が1つだけの無限平面三角形分割は、ユークリッド平面または双曲平面（両方ではない）のいずれかにパッキングを持つ。ユークリッドの場合、パッキングは相似性を除いて一意であり、双曲面の場合、等長性を除いて一意である。^[13]

円充填定理は、平面でないグラフに一般化されます。G が曲面Sに埋め込むことができるグラフである場合、S上に定曲率 リーマン計量 dと、接触グラフがGと同型である( S、  d ) 上の円充填があります。Sが閉じており (コンパクトで境界がない)、GがSの三角形分割である場合、 ( S、  d ) と充填は、共形同値を除いて一意です。S が球面である場合、この同値性はメビウス変換に依存します。 S が球面である場合、同値性は定数によるスケーリングと等長変換に依存します。一方、 Sの種数が少なくとも 2である場合、同値性は等長変換に依存します。

円充填定理の別の一般化では、隣接する頂点に対応する円の間の指定された交差角で接する条件を置き換えることが含まれます。特にエレガントなバージョンは次のとおりです。Gが有限の3 連結平面グラフ (つまり、多面体グラフ) であるとします。この場合、円充填のペアがあり、一方の交差グラフはGと同型で、もう一方の交差グラフはGの平面双対と同型であり、Gのすべての頂点とそれに隣接する面について、頂点に対応する最初の充填の円は、面に対応する 2 番目の充填の円と直交します。^[14]たとえば、この結果を四面体のグラフに適用すると、任意の 4 つの互いに接する円に対して、それぞれが最初の 4 つのうち 3 つと直交する 4 つの互いに接する円の 2 番目のセットが得られます。^[15]さらに一般化すると、交差角を反転距離に置き換えることで、交差したり接したりするのではなく、互いに分離している必要があるパッキングを指定できるようになります。^[16]

さらに別の種類の一般化では、円以外の形状が許可されます。G  = ( V ,  E ) が有限平面グラフで、Gの各頂点vに 形状 が対応し、この形状が閉単位円に同相で境界が滑らかであるとします。すると、平面に パッキングが存在し、 かつ である場合に限り 、各に対してから平行移動とスケーリングによってセットが得られます。(元の円パッキング定理では、頂点ごとに 3 つの実パラメータがあり、そのうち 2 つは対応する円の中心を記述し、1 つは半径を記述し、辺ごとに 1 つの方程式があることに注意してください。これはこの一般化でも当てはまります。) この一般化の証明の 1 つは、Koebe の元の証明^{[17]と Brandt [18]}および Harrington ^[19]の定理を適用することで得られます。この定理では、平行移動とスケーリングを除けば、任意の有限連結領域は境界成分が指定された形状を持つ平面領域と等角的に同値であるというものです。 ${\displaystyle K_{v}\subset \mathbb {R} ^{2}}$${\displaystyle P=(K'_{v}:v\in V)}$${\displaystyle K'_{v}\cap K'_{u}\neq \varnothing }$${\displaystyle [v,u]\in E}$${\displaystyle v\in V}$${\displaystyle K'_{v}}$${\displaystyle K_{v}}$

円充填は、1910年にアーノルド・エムチの葉序におけるドイル螺旋（植物の成長の数学）の研究で早くも研究されていました。[ 20 ^{]円充填定理は、}ポール・ケーベによって初めて証明されました。^[17]ウィリアム・サーストン^[1]は 円充填定理を再発見し、それがEMアンドレーエフの研究から導かれることを指摘しました。サーストンはまた、円充填定理を使用して、平面の単連結な真部分集合の単位円の内部への同相写像を得るためのスキームを提案しました。円充填に関するサーストン予想は、円の半径がゼロに近づくにつれて同相写像がリーマン写像に収束するという彼の予想です。サーストン予想は後にバートン・ロダンとデニス・サリバンによって証明されました。^[21] これにより、円充填定理の拡張、等角写像との関係、および応用に関する研究が活発に行われるようになった。

• アポロニアンガスケット、三角形の隙間を繰り返し埋めることで形成される無限のパッキング
• 円の詰め込み、特定の接線を持たない円の密な配置
• ドイル螺旋、無限6正則平面グラフを表す円充填
• フォード円、有理数直線に沿った円の詰め合わせ
• ペニーグラフ、すべての円の半径が等しいコイングラフ
• 環の補題、パッキングにおける隣接する円の大きさの上限

• Andreev, EM (1970)、「Lobačevskiĭ 空間の凸多面体」、Mat. Sb.、New Series、81 (123): 445–478、Bibcode :1970SbMat..10..413A、doi :10.1070/SM1970v010n03ABEH001677、MR  0259734
• ベアドン、アラン F.; スティーブンソン、ケネス (1990)、「円パッキングの均一化定理」、インディアナ大学数学ジャーナル、39 (4): 1383–1425、doi : 10.1512/iumj.1990.39.39062
• ベアドン、アラン F.; スティーブンソン、ケネス (1991)、「円充填のためのシュワルツ-ピック補題」、イリノイ J. 数学、35 (4): 577–606、doi : 10.1215/ijm/1255987673
• Andreev, EM (1970)、「Lobačevskiĭ 空間における有限体積の凸多面体」、Mat. Sb.、New Series、83 (125): 256–260、Bibcode :1970SbMat..12..255A、doi :10.1070/SM1970v012n02ABEH000920、MR  0273510
• ベンジャミニ、イタイ;シュラム、オデッド(2001)、「有限平面グラフの分布限界の再発」、電子確率ジャーナル、6、doi : 10.1214/EJP.v6-96、MR  1873300、S2CID  2862151
• Bowers, Philip L.; Stephenson, Kenneth (2004)、「8.2 逆距離パッキング」、円パッキングによるデッサンとベリイ マップの均一化、アメリカ数学会誌、第 170 巻、pp. 78–82、doi :10.1090/memo/0805、MR  2053391
• Brandt、M. (1980)、「Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete」、Bull。デ・ラ・ソック。デス・シーEt des Letter.デウツ、30
• ブライトウェル、グラハム R.;シェイナーマン、エドワード R. (1993)、「平面グラフの表現」、SIAM J. 離散数学、6 (2): 214–229、doi :10.1137/0406017
• カーター、イシエル、ロダン、バート (1992)、「円パッキングと等角写像の逆問題」、アメリカ数学会誌、334 (2): 861–875、doi : 10.1090/S0002-9947-1992-1081937-X
• Colin de Verdière、Yves (1991)、「Une principevariationnel pour les empilements de cercles」、Inventiones Mathematicae、104 (1): 655–669、Bibcode :1991InMat.104..655C、doi :10.1007/BF01245096、S2CID  121028882
• コリンズ、チャールズ R.; スティーブンソン、ケネス (2003)、「サークルパッキングアルゴリズム」、計算幾何学。理論と応用、25 (3): 233–256、doi : 10.1016/S0925-7721(02)00099-8、MR  1975216
• Coxeter, HSM (2006)、「互いに接する 4 つの円の絶対特性」、非ユークリッド幾何学、Math. Appl. (NY)、vol. 581、ニューヨーク: Springer、pp. 109–114、doi :10.1007/0-387-29555-0_5、MR  2191243
• Emch、Arnold (1910)、「Sur quelques exemples mathématiques dans les Sciences Naturelles」、L'Enseignement mathématique (フランス語)、12 : 114–123
• ハリントン、アンドリュー N. (1982)、「任意に指定された境界形状を持つ領域への等角写像」、Journal d'Analyse Mathématique、41 (1): 39–53、doi : 10.1007/BF02803393、S2CID  120752035
• He, Zheng-Xu; Schramm, O. (1995)、「双曲型および放物型パッキング」、Discrete & Computational Geometry、14 (2): 123–149、doi :10.1007/BF02570699、MR  1331923
• ヨナソン、ヨハン;シュラム、オデッド(2000)、「平面グラフの被覆時間について」、電子通信確率、5 : 85–90
• ケルナー、ジョナサン A. (2006)、「有界種数のグラフのスペクトル分割、固有値境界、円パッキング」、SIAM Journal on Computing、35 (4): 882–902、doi :10.1137/S0097539705447244、hdl : 1721.1/30169
• ケシェグ、バラズ。Pach, ヤーノス; Pálvölgyi、Dömötör (2011)、「傾斜がほとんどない境界次数の平面グラフの描画」、Brandes、Ulrik ; Cornelsen、Sabine (編)、Graph Drawing: 18th International Symposium、GD 2010、コンスタンツ、ドイツ、2010 年 9 月 21 ～ 24 日、改訂された厳選論文、コンピュータ サイエンスの講義ノート、vol. 6502、ハイデルベルク: Springer、pp. 293–304、arXiv : 1009.1315、doi :10.1007/978-3-642-18469-7_27、MR  2781274、S2CID  817874
• Koebe、Paul (1936)、「Kontaktprobleme der Konformen Abbildung」、Ber。ザックス。アカド。ウィス。ライプツィヒ、数学-物理学。 Kl.、88 : 141–164
• リプトン、リチャード J. ;タージャン、ロバート E. (1979)、「平面グラフのセパレータ定理」、SIAM Journal on Applied Mathematics、36 (2): 177–189、CiteSeerX  10.1.1.104.6528、doi :10.1137/0136016
• マリッツ、セス; パパコスタス、アキレアス (1994)、「平面グラフの角度分解能について」、SIAM Journal on Discrete Mathematics、7 (2): 172–183、doi :10.1137/S0895480193242931、MR  1271989
• ミラー、ゲイリー L. ;テン、シャンホア;サーストン、ウィリアム; ヴァヴァシス、スティーブン A. (1997)、「球パッキングと最近傍グラフのセパレータ」、J. ACM、44 (1): 1–29、doi : 10.1145/256292.256294、S2CID  17331739
• モハール、ボジャン（1993）、「多項式時間サークルパッキングアルゴリズム」、離散数学、117（1–3）：257–263、doi：10.1016/0012-365X（93）90340-Y
• ロダン、バートン、サリバン、デニス(1987)、「円パッキングのリーマン写像への収束」、微分幾何学ジャーナル、26 (2): 349–360、doi : 10.4310/jdg/1214441375
• ローデ、ステフェン (2011)、「オデッド・シュラム：サークルパッキングから SLE へ」、Ann. Probab.、39 (5​​): 1621–1667、arXiv : 1007.2007、doi : 10.1214/10-AOP590
• Stephenson, Kenneth (1999)、「円パッキングによる共形構造の近似」(PDF)、Computational methods and function theory 1997 (Nicosia)、Ser. approx. Decompos.、vol. 11、World Sci. Publ.、River Edge、NJ、pp. 551–582、MR  1700374
• スティーブンソン、ケン (2003)、「サークルパッキング：数学の物語」（PDF）、Notices Amer. Math. Soc.、50：1376–1388
• スティーブンソン、ケン（2005）、サークルパッキング入門、離散解析関数の理論、ケンブリッジ：ケンブリッジ大学出版局
• サーストン、ウィリアム(1985)、「有限リーマン写像定理」、ビーバーバッハ予想の証明を記念したパデュー大学国際シンポジウムでの招待講演
• サーストン、ウィリアム（1978-1981）、3次元多様体の幾何学と位相、プリンストン講義ノート

• CirclePack (グラフから円パッキングを作成するための無料ソフトウェア) と、テネシー大学の Kenneth Stephenson による円パッキングの参考文献