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

【れべる (level)】

$d\,$次元超平面アレンジメントにおいて, $x_{d}\,$軸に平行な直線で貫いたときに下から $k\,$番目となる交点をもつフェイス全体の集合を, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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})\,$時間で 求める平面走査法アルゴリズムが知られている.