「レベル (計算幾何における)」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【れべる (level)】''' $d$次元超平面アレンジメントにおいて, $x_d$軸に平行な直線で貫いたときに下から $k$番目となる交点をもつ...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
'''【れべる (level)】''' | '''【れべる (level)】''' | ||
| − | + | <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次元の場合, 高々までのレベルのサイズはであり, -レベルのサイズはとなる. 双対性より, これは平面の 点を直線で等分割する方法の数がであることも意味する. -レベルを時間で 求める平面走査法アルゴリズムが知られている.
