一般的な位置にn個の線分があるとします。n個のセグメントごとに、交差する他のn-1個の数をすばやく数えるにはどうすればよいですか？
私はこれをO（n 2）時間で素朴に行うことができます。O（（n + k）log n）時間でかなり単純なスイープラインアルゴリズム（Bentley-Ottmann）を使用してすべての交差点を見つけることができます。ここで、kはそのような交差点の数であり、見つけた交差点をカウントします。
ただし、交差点を見つける必要はありません。いくつあるか知りたいだけです。交差点ごとにツリー内の2つのものを並べ替える必要があるため、スイープラインアルゴリズムをより高速に変更する方法がわかりません。また、同じ問題が発生しない他の手法は考えられません。
交差点の総数を数える方法にも興味があります。
一般的なケースで、あなたがベントレー オットマンよりも優れているとは信じがたいです。線分が交差する場所を気にしない場合は、計算を少し単純化できますが、交差を見つけずに交差をカウントする方法がわかりません。
要するに、Bentley Ottman は交差点の検索スペースを簡素化する方法です。線分の特定の配置で機能する方法は他にもありますが、線分間に予測可能な幾何学的関係がない限り、交差候補を見つける賢い方法を最初に使用するよりもうまくいくことはありません各候補者の個別検証。
問題のドメインに、悪用可能なサブ構造を提供する可能性のある特定の機能がない限り、速度の最善の策は、Bentley Ottman (または同様のスイープ アルゴリズム) を並列実行に適応させることだと思います。(線分をバンドにクリッピングするのは簡単です。最適なバンドのセットを見つけ出すのも興味深いでしょう。) もちろん、これは学問的課題ではなく実践的な課題です。並列アルゴリズムは、合計でより多くの作業を行うことになる可能性があります。ハードウェアを利用して、（一定の係数で）より短い時間で作業を行うだけです。