計算幾何学における線の交点と線の配置の問題に関する文献を簡単に見直しました。それらのほとんどは、平面スイープ アルゴリズムに基づいています。計算の複雑さの観点から、漸近的なアルゴリズムの境界は、線分の数と項「k」の関数であると思われます。ここで、「k」はエッジ間の交点の数です。たとえば、最もよく知られているアルゴリズムの 1 つは、出力に依存する O(nlogn + "k") の時間複雑度を持っています。私の問題は、時間の複雑さを提供しながら「k」という用語を取り除くことができないという事実を理解するのが難しいことです。並べ替えの問題などの他のアルゴリズムを見ると、複雑さはスワップまたは比較が行われる回数の関数ではないためです。これは単純に入力数の関数です。