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

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【あれんじめんと (arrangement) 】''' 　超平面のアレンジメント(hyperplane arrangement) とは, 超平面による空間の 分割である. [[双対変...')
 
 
(4人の利用者による、間の5版が非表示)
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$のアレンジメントといい, ${\cal A}(H)$と書く. フェイスの次元を明記したいときは, $k$次元$(0\allowbreak \le k\le d)$のフェイスを$k$-フェイスと書く. $0$-フェイスを頂点, $1$-フェイスを辺, $(d-1)$-フェイスを ファセット (facet), $d$-フェイスをセル (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) とも呼ぶ.   
  
−
　フェイス$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>{\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>は, アレンジメントが単純であるとき達成され,   
  
  
−
f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}  
+
<center>
 +
<math>f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}\, </math>
 +
</center>
  
  
−
で与えられる. 特に, $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>\textstyle f_d(H) ={\sum}_{i=0}^d {n\choose d-i}={\rm O}(n^d)\, </math>となる.   
  
−
　アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の$n$本の直線からなる単純なアレンジメントを構成する方法を述べる.   
+
　アレンジメントは逐次添加法で構成できる. 超平面を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>と交わる面の境界上で 辿る辺の数に比例する.
  
−
　$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$と交わる面の境界上で 辿る辺の数に比例する.  
+
　<math>d\, </math>次元の<math>n\, </math>個の超平面のアレンジメントにおいて, 新たに1つ超平面<math>h\, </math>を加え, <math>h\, </math>と交わる各セルのフェイスの集合を[[ゾーン]]と定義すると, 次のゾーン定理が成り立つ.
  
−
　$d$次元の$n$個の超平面のアレンジメントにおいて, 新たに1つ超平面$h$を加え, $h$と交わる各セルのフェイスの集合を[[ゾーン]]と定義すると, 次のゾーン定理が成り立つ.   
+
[[ゾーン定理]]. <math>d\, </math>次元空間内の<math>n\, </math>個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は<math>{\rm O}(n^{d-1})\, </math>である.   
  
−
[[ゾーン定理]]. $d$次元空間内の$n$個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数は${\rm O}(n^{d-1})$である.   
+
　このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を <math>{\rm O}(n^d)\, </math>でおさえることができる.   
  
−
　このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を ${\rm O}(n^d)$でおさえることができる.   
+
　ゾーン定理の離散幾何への応用を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次元の場合には, このような関係から複数のセルの辺の数を評価することができる.   
  
−
ゾーン定理の離散幾何への応用を1つ上げておく. 
+
　<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>時間で求める 平面走査法アルゴリズムが知られている.   
−
$d$次元の$n$超平面のアレンジメントのセルの集合を ${\cal C}$, 各セル$c\in {\cal 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次元の平面のアレンジメントでもレベルのサイズは<math>{\rm o}(n^3)\, </math>である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成される[[スケルトン]]をたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある.   
−
 
 
−
　3次元の平面のアレンジメントでもレベルのサイズは${\rm o}(n^3)$である. 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.
 +
 +
[[Category:計算幾何|あれんじめんと]]

2007年8月7日 (火) 02:12時点における最新版

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

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

　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 次元ユークリッド空間内の個の超平面(の場合は直線) の集合を考える. このによって, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathbf R}^d\, } はいろいろな次元のフェイス (face) に分割される. 例えば, 2次元内の有限個の直線の集合は, 2次元, 1次元, 0次元のフェイス (面, 辺, 点) に平面を自然に分割する. これらのフェイスの集合とその接続関係, 各フェイスに対しそれを含む超平面の情報を合わせたものを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H\, } のアレンジメントといい, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal A}(H)\, } と書く. フェイスの次元を明記したいときは, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } 次元構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (0 \le k\le d)\, } のフェイスを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } -フェイスと書く. -フェイスを頂点, -フェイスを辺, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (d-1)\, } -フェイスを ファセット (facet), 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } -フェイスをセル (cell) とも呼ぶ.

　フェイス構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } がフェイスの部分フェイスであるとは, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } の次元が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } の次元 より1だけ小さく, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } がの境界に含まれていることである. がの部 分フェイスならば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle g\, } は (互いに) 接続しているといい, この関係 を接続関係という. フェイスの接続関係全体は束をなし, アレンジメントは, 各フェイスの座標など幾何情報と, このフェイスのなす束で表される.

　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathbf R}^d\, } 内の個の超平面のアレンジメントが単純 (simple) である とは, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H\, } に属する任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 個の超平面は1点で交わり, どの構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d+1\, } 個の超平面 も共通の交点をもたないことである. アレンジメントの構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } -フェイスの最大数は, アレンジメントが単純であるとき達成され,


構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f_k(H)=\sum_{i=0}^k {d-i\choose k-i}{n\choose d-i}\, }


で与えられる. 特に, -フェイス, すなわちセルの数は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } を定数とみなすと 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle f_d(H) ={\sum}_{i=0}^d {n\choose d-i}={\rm O}(n^d)\, } となる.

　アレンジメントは逐次添加法で構成できる. 超平面を1つずつ付け加え, アレンジメントの接続関係を更新していく方法である. 2次元の場合で, 平面上の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 本の直線からなる単純なアレンジメントを構成する方法を述べる. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 本の直線の集合を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle L=\{ l_1,l_2,\cdots ,l_n\}\, } とし, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x,y)\, } 平面上にあるとする. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k-1\, } 本の直線構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle l_1,\cdots ,l_{k-1}\, } からなるアレンジメントに構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } 番目の 直線構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle l_k\, } を加えてアレンジメントを更新する. 各頂点には, この頂点に接続している4つの辺を反時計回りの 順で貯えておく. 各辺には, その辺を含む直線の式と辺の両端点の頂点を覚えておく. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x=-\infty\, } で構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle l_k\, } のすぐ上にある直線を左から辿り, この辺の下に接続している面の境界を時計回りに回って行く. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle l_k\, } と交わった時は, その交点から始めて, 今度は隣の面の境界 を時計回りに辿る. これを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle l_k\, } がすでにアレンジメントに存在していた 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k-1\, } 本の直線と交わるまで行なう. この操作により, 上に新たに現れる頂点もすべて列挙することができ, そこでアレンジメントを更新していくことができる. その手間は, 直線と交わる面の境界上で 辿る辺の数に比例する.

　次元の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 個の超平面のアレンジメントにおいて, 新たに1つ超平面構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h\, } を加え, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle h\, } と交わる各セルのフェイスの集合をゾーンと定義すると, 次のゾーン定理が成り立つ.

ゾーン定理. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 次元空間内の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 個の超平面から成るアレンジメントにおいて, 1つの超平面のゾーンのフェイスの総数はである.

　このゾーン定理より, アレンジメントを逐次添加法で構成したときの計算量を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(n^d)\, } でおさえることができる.

　ゾーン定理の離散幾何への応用を1つ上げておく. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 次元の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 超平面のアレンジメントのセルの集合を 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathcal C}\, } , 各セル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c\in {\mathcal C}\, } のファセットの数を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d(c)\, } としたとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \textstyle {\sum}_{c\in{\mathcal C}}d(c)^2={\rm O}(n^d)\, } が成り立つ. であるから, 各セルのファセットの数はそんなに分散が大きくないことが わかる. 2次元の場合には, このような関係から複数のセルの辺の数を評価することができる.

　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 次元超平面アレンジメントにおいて, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_d\, } 軸に平行な直線で貫いたときに下から構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } 番目となる交点をもつフェイス全体の集合を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } -レベル, または単にレベル という. 2次元の場合, 高々構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } までのレベルのサイズは構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(kn)\, } であり, -レベルのサイズは構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(\sqrt{k}n)\, } となる. 双対性より, これは平面の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } 点を直線で等分割する方法の数が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(n^{1.5})\, } であることも 意味する. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } -レベルを 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm O}(\sqrt{k}n(\log n)^2)\, } 時間で求める 平面走査法アルゴリズムが知られている.

　3次元の平面のアレンジメントでもレベルのサイズは構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\rm o}(n^3)\, } である. 4次元以上の 場合, 全体より小さいオーダであるかどうかはわかっていない. また, 高次元の場合 は, 0, 1次元フェイスの頂点, 辺で構成されるスケルトンをたどるアルゴリズムも知られており, 特に3次元ではアレンジメント全体を 求めるよりも効率よく計算できる. レベルや1つのセルのスケルトンも 有用で, 点集合の問題を双対変 換して解いている場合, スケルトンのみで十分な場合もある.

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


参考文献

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=《アレンジメント》&oldid=7799」から取得