「レベル (計算幾何における)」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(他の1人の利用者による、間の1版が非表示)
2行目: 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>時間で 求める平面走査法アルゴリズムが知られている.
 +
 +
[[Category:計算幾何|れべる]]

2008年11月14日 (金) 09:46時点における最新版

【れべる (level)】

次元超平面アレンジメントにおいて, 軸に平行な直線で貫いたときに下から 番目となる交点をもつフェイス全体の集合を, -レベル, または単にレベルという. 2次元の場合, 高々までのレベルのサイズはであり, -レベルのサイズはとなる. 双対性より, これは平面の 点を直線で等分割する方法の数がであることも意味する. -レベルを時間で 求める平面走査法アルゴリズムが知られている.