「アレンジメント」の版間の差分
(基礎編と用語編のマージ) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
'''【あれんじめんと (arrangement)】''' | '''【あれんじめんと (arrangement)】''' | ||
| + | === 概要 === | ||
超平面のアレンジメントとは, 有限個の超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, アレンジメント構造は点集合上の関係構造にも対応する. また, 有向マトロイドの線形な表現でもある. アレンジメントのフェイスの数の数え上げや, 実際にその構造を求めることは, 離散・計算幾何の基礎となっており, ゾーン定理や, <math>k \,</math>-集合に関係するレベルなど種々の有用な定理が知られている. | 超平面のアレンジメントとは, 有限個の超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, アレンジメント構造は点集合上の関係構造にも対応する. また, 有向マトロイドの線形な表現でもある. アレンジメントのフェイスの数の数え上げや, 実際にその構造を求めることは, 離散・計算幾何の基礎となっており, ゾーン定理や, <math>k \,</math>-集合に関係するレベルなど種々の有用な定理が知られている. | ||
| + | |||
| + | === 詳説 === | ||
| + | 超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. [[双対変換]]によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある. | ||
| + | |||
| + | <math>d\, </math>次元ユークリッド空間<math>{\mathbf R}^d\, </math>内の<math>n\, </math>個の超平面(<math>d=2\, \, </math>の場合は直線) の集合<math>H\, </math>を考える. この<math>H\, </math>によって, <math>{\mathbf R}^d\, </math>はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものを<math>H\, </math>のアレンジメントといい, <math>{\mathcal A}(H)\, </math>と書く. フェイスの次元を明記したいときは, <math>k\, </math>次元<math>(0 \le k\le d)\, </math>のフェイスを<math>k\, </math>-フェイスと書く. <math>0\, </math>-フェイスを頂点, <math>1\, </math>-フェイスを辺, <math>(d-1)\, </math>-フェイスを ファセット (facet), <math>d\, </math>-フェイスをセル (cell) とも呼ぶ. | ||
| + | |||
| + | フェイス<math>f\, </math>がフェイス<math>g\, </math>の部分フェイスであるとは, <math>f\, </math>の次元が<math>g\, </math>の次元 より1だけ小さく, <math>f\, </math>が<math>g\, </math>の境界に含まれていることである. <math>f\, </math>が<math>g\, </math>の部 分フェイスならば, <math>f\, </math>と<math>g\, </math>は (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される. | ||
| + | |||
| + | <math>{\mathbf R}^d\, </math>内の<math>n\ge d\, </math>個の超平面のアレンジメントが単純 (simple) である とは, <math>H\, </math>に属する任意の<math>d\, </math>個の超平面は1点で交わり, どの<math>d+1\, </math>個の超平面 も共通の交点をもたないことである. アレンジメントの<math>k\, </math>-フェイスの最大数<math>f_k(H)\, </math>は, アレンジメントが単純であるとき達成され, | ||
| + | |||
| + | |||
| + | <center> | ||
| + | <math>f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}\, </math> | ||
| + | </center> | ||
| + | |||
| + | |||
| + | で与えられる. 特に, <math>d\, </math>-フェイス, すなわちセルの数は<math>d\, </math>を定数とみなすと <math>\textstyle f_d(H) ={\sum}_{i=0}^d {n\choose d-i}={\rm O}(n^d)\, </math>となる. | ||
| + | |||
| + | アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の<math>n\, </math>本の直線からなる単純なアレンジメントを構成する方法を述べる. <math>n\, </math>本の直線の集合を<math>L=\{ l_1,l_2,\cdots ,l_n\}\, </math>とし, <math>(x,y)\, </math>平面上にあるとする. <math>k-1\, </math>本の直線<math>l_1,\cdots ,l_{k-1}\, </math>からなるアレンジメントに<math>k\, </math>番目の 直線<math>l_k\, </math>を加えてアレンジメントを更新する. 各頂点には, この頂点に接続している4つの辺を反時計回りの 順で貯えておく. 各辺には, その辺を含む直線の式と辺の両端点の頂点を覚えておく. <math>x=-\infty\, </math>で<math>l_k\, </math>のすぐ上にある直線を左から辿り, この辺の下に接続している面の境界を時計回りに回って行く. <math>l_k\, </math>と交わった時は, その交点から始めて, 今度は隣の面の境界 を時計回りに辿る. これを<math>l_k\, </math>がすでにアレンジメントに存在していた <math>k-1\, </math>本の直線と交わるまで行なう. この操作により, <math>l_k\, </math>上に新たに現れる頂点もすべて列挙することができ, そこでアレンジメントを更新していくことができる. その手間は, 直線<math>l_k\, </math>と交わる面の境界上で 辿る辺の数に比例する. | ||
| + | |||
| + | <math>d\, </math>次元の<math>n\, </math>個の超平面のアレンジメントにおいて, 新たに1つ超平面<math>h\, </math>を加え, <math>h\, </math>と交わる各セルのフェイスの集合を[[ゾーン]]と定義すると, 次のゾーン定理が成り立つ. | ||
| + | |||
| + | [[ゾーン定理]]. <math>d\, </math>次元空間内の<math>n\, </math>個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は<math>{\rm O}(n^{d-1})\, </math>である. | ||
| + | |||
| + | このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を <math>{\rm O}(n^d)\, </math>でおさえることができる. | ||
| + | |||
| + | ゾーン定理の離散幾何への応用を1つ上げておく. <math>d\, </math>次元の<math>n\, </math>超平面のアレンジメントのセルの集合を <math>{\mathcal C}\, </math>, 各セル<math>c\in {\mathcal C}\, </math>のファセットの数を<math>d(c)\, </math>としたとき, <math>\textstyle {\sum}_{c\in{\mathcal C}}d(c)^2={\rm O}(n^d)\, </math>が成り立つ. <math>\textstyle {\sum}_{c\in{\mathcal C}}d(c)={\rm O}(n^d)\, </math> であるから, 各セルのファセットの数はそんなに分散が大きくないことが わかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる. | ||
| + | |||
| + | <math>d\, </math>次元超平面アレンジメントにおいて, <math>x_d\, </math>軸に平行な直線で貫いたときに下から<math>k\, </math>番目となる交点をもつフェイス全体の集合を<math>k\, </math>-レベル, または単に[[レベル (計算幾何における)|レベル]] という. 2次元の場合, 高々<math>k\, </math>までのレベルのサイズは<math>{\rm O}(kn)\, </math>であり, <math>k\, </math>-レベルのサイズは<math>{\rm O}(\sqrt{k}n)\, </math>となる. 双対性より, これは平面の<math>n\, </math>点を直線で等分割する方法の数が<math>{\rm O}(n^{1.5})\, </math>であることも 意味する. <math>k\, </math>-レベルを <math>{\rm O}(\sqrt{k}n(\log n)^2)\, </math>時間で求める 平面走査法アルゴリズムが知られている. | ||
| + | |||
| + | 3次元の平面のアレンジメントでもレベルのサイズは<math>{\rm o}(n^3)\, </math>である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成される[[スケルトン]]をたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある. | ||
| + | |||
| + | 曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの 組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は 一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる. | ||
| + | |||
| + | |||
| + | |||
| + | ---- | ||
| + | '''参考文献''' | ||
| + | |||
| + | [1] H. Edelsbrunner, ''Algorithms in Combinatorial Geometry,'' Springer-Verlag, 1987. 邦訳 (今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』, 共立出版, 1995. | ||
| + | |||
| + | [[Category:計算幾何|あれんじめんと]] | ||
2008年3月13日 (木) 23:22時点における最新版
【あれんじめんと (arrangement)】
概要
超平面のアレンジメントとは, 有限個の超平面による空間の分割である. 双対変換によって, 点集合は超平面集合に変換されるので, アレンジメント構造は点集合上の関係構造にも対応する. また, 有向マトロイドの線形な表現でもある. アレンジメントのフェイスの数の数え上げや, 実際にその構造を求めることは, 離散・計算幾何の基礎となっており, ゾーン定理や, -集合に関係するレベルなど種々の有用な定理が知られている.
詳説
超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. 双対変換によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある.
次元ユークリッド空間内の個の超平面(の場合は直線) の集合を考える. このによって, はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものをのアレンジメントといい, と書く. フェイスの次元を明記したいときは, 次元のフェイスを-フェイスと書く. -フェイスを頂点, -フェイスを辺, -フェイスを ファセット (facet), -フェイスをセル (cell) とも呼ぶ.
フェイスがフェイスの部分フェイスであるとは, の次元がの次元 より1だけ小さく, がの境界に含まれていることである. がの部 分フェイスならば, とは (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される.
内の個の超平面のアレンジメントが単純 (simple) である とは, に属する任意の個の超平面は1点で交わり, どの個の超平面 も共通の交点をもたないことである. アレンジメントの-フェイスの最大数は, アレンジメントが単純であるとき達成され,
で与えられる. 特に, -フェイス, すなわちセルの数はを定数とみなすと となる.
アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の本の直線からなる単純なアレンジメントを構成する方法を述べる. 本の直線の集合をとし, 平面上にあるとする. 本の直線からなるアレンジメントに番目の 直線を加えてアレンジメントを更新する. 各頂点には, この頂点に接続している4つの辺を反時計回りの 順で貯えておく. 各辺には, その辺を含む直線の式と辺の両端点の頂点を覚えておく. でのすぐ上にある直線を左から辿り, この辺の下に接続している面の境界を時計回りに回って行く. と交わった時は, その交点から始めて, 今度は隣の面の境界 を時計回りに辿る. これをがすでにアレンジメントに存在していた 本の直線と交わるまで行なう. この操作により, 上に新たに現れる頂点もすべて列挙することができ, そこでアレンジメントを更新していくことができる. その手間は, 直線と交わる面の境界上で 辿る辺の数に比例する.
次元の個の超平面のアレンジメントにおいて, 新たに1つ超平面を加え, と交わる各セルのフェイスの集合をゾーンと定義すると, 次のゾーン定理が成り立つ.
ゾーン定理. 次元空間内の個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数はである.
このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を でおさえることができる.
ゾーン定理の離散幾何への応用を1つ上げておく. 次元の超平面のアレンジメントのセルの集合を , 各セルのファセットの数をとしたとき, が成り立つ. であるから, 各セルのファセットの数はそんなに分散が大きくないことが わかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる.
次元超平面アレンジメントにおいて, 軸に平行な直線で貫いたときに下から番目となる交点をもつフェイス全体の集合を-レベル, または単にレベル という. 2次元の場合, 高々までのレベルのサイズはであり, -レベルのサイズはとなる. 双対性より, これは平面の点を直線で等分割する方法の数がであることも 意味する. -レベルを 時間で求める 平面走査法アルゴリズムが知られている.
3次元の平面のアレンジメントでもレベルのサイズはである. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成されるスケルトンをたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある.
曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの 組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は 一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる.
参考文献
[1] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987. 邦訳 (今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』, 共立出版, 1995.