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

出典: ORWiki

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