《アレンジメント》

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

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

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

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

　$${\bf {R}}^{d}$$内の$$n\geq 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$$を定数とみなすと $構文解析に失敗 (不明な関数「\allowbreak」): {\displaystyle f_d(H)\allowbreak =\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)$$としたとき, $$\sum _{c\in {\cal {C}}}d(c)^{2}={\rm {O}}(n^{d})$$ が成り立つ. $ $\sum _{c\in {\cal {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.