レベル (計算幾何における)のソースを表示

'''【れべる (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:計算幾何|れべる]]