レベル (計算幾何における)

【れべる (level)】

$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)$時間で 求める平面走査法アルゴリズムが知られている.