「《アレンジメント》」の版間の差分
(新しいページ: ''''【あれんじめんと (arrangement) 】''' 超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. [[双対変...') |
|||
| 3行目: | 3行目: | ||
超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. [[双対変換]]によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある. | 超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. [[双対変換]]によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある. | ||
| − | $d$次元ユークリッド空間${\bf R}^d$内の$n$個の超平面($d=2$の場合は直線) の集合$H$を考える. この$H$によって, ${\bf R}^d$はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものを$H$のアレンジメントといい, ${\ | + | $<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) とも呼ぶ. |
| − | フェイス$f$がフェイス$g$の部分フェイスであるとは, $f$の次元が$g$の次元 より1だけ小さく, $f$が$g$の境界に含まれていることである. $f$が$g$の部 分フェイスならば, $f$と$g$は (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される. | + | フェイス$<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>$は (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される. |
| − | ${\bf R}^d$内の$n\ge d$個の超平面のアレンジメントが単純 (simple) である とは, $H$に属する任意の$d$個の超平面は1点で交わり, どの$d+1$個の超平面 も交点をもたないことである. アレンジメントの$k$-フェイスの最大数$f_k(H)$は, | + | $<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>$は, アレンジメントが単純であるとき達成され, |
| − | f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i} | + | :<math>f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}</math> |
| − | で与えられる. 特に, $d$-フェイス, すなわちセルの数は$d$を定数とみなすと $f_d(H)\allowbreak =\sum_{i=0}^d {n\choose d-i}={\rm O}(n^d)$となる. | + | で与えられる. 特に, $<math>d</math>$-フェイス, すなわちセルの数は$<math>d</math>$を定数とみなすと $<math>f_d(H)\allowbreak =\sum_{i=0}^d {n\choose d-i}={\rm O}(n^d)</math>$となる. |
| − | アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の$n$本の直線からなる単純なアレンジメントを構成する方法を述べる. | + | アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の<math>$n</math>$本の直線からなる単純なアレンジメントを構成する方法を述べる. |
| − | $n$本の直線の集合を$L=\{ l_1,l_2,\cdots ,l_n\}$とし, $(x,y)$平面上にあるとする. $k-1$本の直線$l_1,\cdots ,l_{k-1}$からなるアレンジメントに$k$番目の 直線$l_k$を加えてアレンジメントを更新する. 各頂点には, この頂点に接続している4つの辺を反時計回りの 順で貯えておく. 各辺には, | + | $<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>$と交わる面の境界上で 辿る辺の数に比例する. |
| − | $d$次元の$n$個の超平面のアレンジメントにおいて, 新たに1つ超平面$h$を加え, $h$と交わる各セルのフェイスの集合を[[ゾーン]]と定義すると, 次のゾーン定理が成り立つ. | + | $<math>d</math>$次元の$<math>n</math>$個の超平面のアレンジメントにおいて, 新たに1つ超平面$<math>h</math>$を加え, $<math>h</math>$と交わる各セルのフェイスの集合を[[ゾーン]]と定義すると, 次のゾーン定理が成り立つ. |
| − | [[ゾーン定理]]. $d$次元空間内の$n$個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は${\rm O}(n^{d-1})$である. | + | [[ゾーン定理]]. $<math>d</math>$次元空間内の$<math>n</math>$個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は$<math>{\rm O}(n^{d-1})</math>$である. |
| − | このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を ${\rm O}(n^d)$でおさえることができる. | + | このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を $<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{\cal C}}d(c)^2={\rm O}(n^d)</math>$ が成り立つ. $ <math>\sum_{c\in{\cal C}}d(c)={\rm O}(n^d)</math> $ であるから, 各セルのファセットの数はそんなに分散が大きくないことが わかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる. | |
| − | $d$次元の$n$超平面のアレンジメントのセルの集合を ${\ | ||
| − | $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)$時間で求める 平面走査法アルゴリズムが知られている. | + | $<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次元の平面のアレンジメントでもレベルのサイズは${\rm o}(n^3)$である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成される[[スケルトン]]をたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある. | + | 3次元の平面のアレンジメントでもレベルのサイズは$<math>{\rm o}(n^3)</math>$である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成される[[スケルトン]]をたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある. |
曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの 組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は 一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる. | 曲線・曲面のアレンジメントも有用であり, このアレンジメントの1つのセルやゾーンの 組合せ複雑度の解析は, Davenport-Schinzel列の理論としてまとめられている. 定数次数の代数曲線のアレンジメントでは, セルのフェイス数は 一般次元で全体のオーダよりほぼ1つ小さな次数の数でおさえられる. | ||
| 37行目: | 36行目: | ||
---- | ---- | ||
| − | |||
'''参考文献''' | '''参考文献''' | ||
[1] H. Edelsbrunner, ''Algorithms in Combinatorial Geometry,'' Springer-Verlag, 1987. 邦訳 (今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』, 共立出版, 1995. | [1] H. Edelsbrunner, ''Algorithms in Combinatorial Geometry,'' Springer-Verlag, 1987. 邦訳 (今井浩, 今井桂子訳), 『組合せ幾何学のアルゴリズム』, 共立出版, 1995. | ||
2007年7月6日 (金) 21:19時点における版
【あれんじめんと (arrangement) 】
超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. 双対変換によって, 点集合は超平面集合に変換されるので, 点集合の問題にも対応する. また, 離散システムの観 点からは, 線形有向マトロイドの1つの表現である. 組合せ幾何とアルゴリズ ムからの詳しい解説が [1] にある.
$$次元ユークリッド空間$$内の$$個の超平面($$の場合は直線) の集合$$を考える. この$$によって, $はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものを$$のアレンジメントといい, $$と書く. フェイスの次元を明記したいときは, $$次元構文解析に失敗 (不明な関数「\allowbreak」): {\displaystyle $(0\allowbreak \le k\le d)$} のフェイスを$$-フェイスと書く. $$-フェイスを頂点, $$-フェイスを辺, $$-フェイスを ファセット (facet), $$-フェイスをセル (cell) とも呼ぶ.
フェイス$$がフェイス$の部分フェイスであるとは, $$の次元が$$の次元 より1だけ小さく, $$が$$の境界に含まれていることである. $が$$の部 分フェイスならば, $$と$$は (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される.
$$内の$$個の超平面のアレンジメントが単純 (simple) である とは, $$に属する任意の$個の超平面は1点で交わり, どの$$個の超平面 も交点をもたないことである. アレンジメントの$$-フェイスの最大数$$は, アレンジメントが単純であるとき達成され,
で与えられる. 特に, $$-フェイス, すなわちセルの数は$$を定数とみなすと $構文解析に失敗 (不明な関数「\allowbreak」): {\displaystyle f_d(H)\allowbreak =\sum_{i=0}^d {n\choose d-i}={\rm O}(n^d)}
$となる.
アレンジメントは逐次添加法で構成できる. 超平面を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.