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

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