「《アレンジメント》」の版間の差分

2007年7月6日 (金) 21:41時点における版

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

　超平面のアレンジメント(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\leq k\leq d)\,$ のフェイスを $k\,$ -フェイスと書く. $0\,$ -フェイスを頂点, $1\,$ -フェイスを辺, $(d-1)\,$ -フェイスをファセット (facet), $d\,$ -フェイスをセル (cell) とも呼ぶ.

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

　 ${\mathbf {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\,$ を定数とみなすと $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)\,$ としたとき, ${\sum }_{c\in {\mathcal {C}}}d(c)^{2}={\rm {O}}(n^{d})\,$ が成り立つ. ${\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.

@@ 3行目: / 3行目: @@
 　超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. [[双対変換]]によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある.
-　$<math>d</math>$次元ユークリッド空間$<math>{\bf R}^d</math>$内の$<math>n</math>$個の超平面($<math>d=2</math>$の場合は直線) の集合$<math>H</math>$を考える. この$<math>H</math>$によって, $<math>{\bf R}^d$</math>はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものを$<math>H</math>$のアレンジメントといい, $<math>{\mathcal A}(H)</math>$と書く. フェイスの次元を明記したいときは, $<math>k</math>$次元<math>$(0\allowbreak \le k\le d)$</math>のフェイスを$<math>k</math>$-フェイスと書く. $<math>0</math>$-フェイスを頂点, $<math>1</math>$-フェイスを辺, $<math>(d-1)</math>$-フェイスを ファセット (facet), $<math>d</math>$-フェイスをセル (cell) とも呼ぶ.
+　<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>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>{\bf 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>$は, アレンジメントが単純であるとき達成され,
+　<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>は, アレンジメントが単純であるとき達成され,
-:<math>f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}</math>
+:<math>f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}\, </math>
-で与えられる. 特に, $<math>d</math>$-フェイス, すなわちセルの数は$<math>d</math>$を定数とみなすと $<math>f_d(H)\allowbreak =\sum_{i=0}^d {n\choose d-i}={\rm O}(n^d)</math>$となる.
+で与えられる. 特に, <math>d\, </math>-フェイス, すなわちセルの数は<math>d\, </math>を定数とみなすと <math>f_d(H) ={\sum}_{i=0}^d {n\choose d-i}={\rm O}(n^d)\, </math>となる.
-　アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の<math>$n</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>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>h</math>$を加え, $<math>h</math>$と交わる各セルのフェイスの集合を[[ゾーン]]と定義すると, 次のゾーン定理が成り立つ.
+[[ゾーン定理]]. <math>d\, </math>次元空間内の<math>n\, </math>個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は<math>{\rm O}(n^{d-1})\, </math>である.
-[[ゾーン定理]]. $<math>d</math>$次元空間内の$<math>n</math>$個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は$<math>{\rm O}(n^{d-1})</math>$である.
+　このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を <math>{\rm O}(n^d)\, </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>{\sum}_{c\in{\mathcal C}}d(c)^2={\rm O}(n^d)\, </math>が成り立つ.  <math>{\sum}_{c\in{\mathcal C}}d(c)={\rm O}(n^d)\, </math>  であるから, 各セルのファセットの数はそんなに分散が大きくないことが わかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる.
-　ゾーン定理の離散幾何への応用を1つ上げておく.  $<math>d</math>$次元の$<math>n</math>$超平面のアレンジメントのセルの集合を $<math>{\mathcal C}</math>$, 各セル$<math>c\in {\mathcal C}</math>$のファセットの数を$<math>d(c)</math>$としたとき,  $<math>\sum_{c\in{\cal C}}d(c)^2={\rm O}(n^d)</math>$ が成り立つ.  $ <math>\sum_{c\in{\cal 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>時間で求める 平面走査法アルゴリズムが知られている.
-　$<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>$時間で求める 平面走査法アルゴリズムが知られている.
+次元の平面のアレンジメントでもレベルのサイズは<math>{\rm o}(n^3)\, </math>である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成される[[スケルトン]]をたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある.
-次元の平面のアレンジメントでもレベルのサイズは$<math>{\rm o}(n^3)</math>$である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成される[[スケルトン]]をたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある.
 　曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの 組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は 一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる.

「《アレンジメント》」の版間の差分

2007年7月6日 (金) 21:41時点における版

案内メニュー

検索