アレンジメント

出典: ORWiki

【あれんじめんと (arrangement)】

概要

超平面のアレンジメントとは, 有限個の超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, アレンジメント構造は点集合上の関係構造にも対応する. また, 有向マトロイドの線形な表現でもある. アレンジメントのフェイスの数の数え上げや, 実際にその構造を求めることは, 離散・計算幾何の基礎となっており, ゾーン定理や, k \,-集合に関係するレベルなど種々の有用な定理が知られている.

詳説

　超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. 双対変換によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある.

　d\,次元ユークリッド空間{\mathbf R}^d\,内のn\,個の超平面(d=2\, \,の場合は直線) の集合H\,を考える. このH\,によって, {\mathbf R}^d\,はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものをH\,のアレンジメントといい, {\mathcal A}(H)\,と書く. フェイスの次元を明記したいときは, k\,次元(0 \le k\le d)\,のフェイスをk\,-フェイスと書く. 0\,-フェイスを頂点, 1\,-フェイスを辺, (d-1)\,-フェイスを ファセット (facet), d\,-フェイスをセル (cell) とも呼ぶ.

　フェイスf\,がフェイスg\,の部分フェイスであるとは, f\,の次元がg\,の次元 より1だけ小さく, f\,がg\,の境界に含まれていることである. f\,がg\,の部 分フェイスならば, f\,とg\,は (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される.

　{\mathbf R}^d\,内のn\ge d\,個の超平面のアレンジメントが単純 (simple) である とは, H\,に属する任意のd\,個の超平面は1点で交わり, どのd+1\,個の超平面 も共通の交点をもたないことである. アレンジメントのk\,-フェイスの最大数f_k(H)\,は, アレンジメントが単純であるとき達成され,


f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}\,


で与えられる. 特に, d\,-フェイス, すなわちセルの数はd\,を定数とみなすと \textstyle f_d(H) ={\sum}_{i=0}^d {n\choose d-i}={\rm O}(n^d)\,となる.

　アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上のn\,本の直線からなる単純なアレンジメントを構成する方法を述べる. n\,本の直線の集合をL=\{ l_1,l_2,\cdots ,l_n\}\,とし, (x,y)\,平面上にあるとする. k-1\,本の直線l_1,\cdots ,l_{k-1}\,からなるアレンジメントにk\,番目の 直線l_k\,を加えてアレンジメントを更新する. 各頂点には, この頂点に接続している4つの辺を反時計回りの 順で貯えておく. 各辺には, その辺を含む直線の式と辺の両端点の頂点を覚えておく. x=-\infty\,でl_k\,のすぐ上にある直線を左から辿り, この辺の下に接続している面の境界を時計回りに回って行く. l_k\,と交わった時は, その交点から始めて, 今度は隣の面の境界 を時計回りに辿る. これをl_k\,がすでにアレンジメントに存在していた k-1\,本の直線と交わるまで行なう. この操作により, l_k\,上に新たに現れる頂点もすべて列挙することができ, そこでアレンジメントを更新していくことができる. その手間は, 直線l_k\,と交わる面の境界上で 辿る辺の数に比例する.

　d\,次元のn\,個の超平面のアレンジメントにおいて, 新たに1つ超平面h\,を加え, h\,と交わる各セルのフェイスの集合をゾーンと定義すると, 次のゾーン定理が成り立つ.

ゾーン定理. d\,次元空間内のn\,個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は{\rm O}(n^{d-1})\,である.

　このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を {\rm O}(n^d)\,でおさえることができる.

　ゾーン定理の離散幾何への応用を1つ上げておく. d\,次元のn\,超平面のアレンジメントのセルの集合を {\mathcal C}\,, 各セルc\in {\mathcal C}\,のファセットの数をd(c)\,としたとき, \textstyle {\sum}_{c\in{\mathcal C}}d(c)^2={\rm O}(n^d)\,が成り立つ. \textstyle {\sum}_{c\in{\mathcal C}}d(c)={\rm O}(n^d)\, であるから, 各セルのファセットの数はそんなに分散が大きくないことが わかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる.

　d\,次元超平面アレンジメントにおいて, x_d\,軸に平行な直線で貫いたときに下からk\,番目となる交点をもつフェイス全体の集合をk\,-レベル, または単にレベル という. 2次元の場合, 高々k\,までのレベルのサイズは{\rm O}(kn)\,であり, k\,-レベルのサイズは{\rm O}(\sqrt{k}n)\,となる. 双対性より, これは平面のn\,点を直線で等分割する方法の数が{\rm O}(n^{1.5})\,であることも 意味する. k\,-レベルを {\rm O}(\sqrt{k}n(\log n)^2)\,時間で求める 平面走査法アルゴリズムが知られている.

　3次元の平面のアレンジメントでもレベルのサイズは{\rm o}(n^3)\,である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成されるスケルトンをたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある.

　曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの 組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は 一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる.


参考文献

[1] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. 邦訳 (今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』, 共立出版, 1995.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%82%A2%E3%83%AC%E3%83%B3%E3%82%B8%E3%83%A1%E3%83%B3%E3%83%88" より作成