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

【れべる (level)】

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