「レベル (計算幾何における)」の版間の差分
ナビゲーションに移動
検索に移動
細 ("レベル (計算幾何における)" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 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次元の場合, 高々までのレベルのサイズはであり, -レベルのサイズはとなる. 双対性より, これは平面の 点を直線で等分割する方法の数がであることも意味する. -レベルを時間で 求める平面走査法アルゴリズムが知られている.
