一般的な位置にn個の線分があるとします。どのようにn個のセグメントのそれぞれについて、他のn-1個のセグメントが交差するかを素早く数えることができますか？与えられた線分の集合の間の交差点の数を数える効率的な方法はありますか？
これは、O（n ）時間でこれを素朴に行うことができます。私はO（（n + k）log n）時間でかなり単純な掃引線アルゴリズム（Bentley-Ottmann）を使ってすべての交差点を見つけることができます。ここでkはこの交差点の数です。数えます
私はを見つける必要はありません。交差点を探してください。私はちょうどそこにいくつあるか知りたい。私は、交差点ごとにツリー内の2つのものを並べ替える必要があるため、掃引線アルゴリズムをより速く修正する方法は見当たりません。同じ問題を抱えていない他のテクニックは考えられません。
また、交差点の総数を計算する方法についても知りたいと思います。
一般的なケースでは、Bentley Ottmanよりも優れていると信じています。線分が交差する場所を気にしなければ計算を少し簡略化できますが、交差点を見つけることなく交差点を数える方法はわかりません。
本質的に、Bentley Ottmanは交差点の検索スペースを単純化する方法です。他の方法もありますが、線分の特定の配置には有効ですが、セグメント間に幾何学的な関係がある場合を除いて、候補交差点を見つけるための賢明な方法を使用するよりも、各候補の個別検証
悪用可能な部分構造を提供する可能性がある特定の機能が問題のドメインに含まれていない限り、Bentley Ottman（または同様のスイープアルゴリズム）をパラレル実行に適応させるのが最善の方法です。 （ラインセグメントをバンドにカットするのは単純なものですが、バンドの最適なセットを見つけることも面白いでしょう）もちろん、これは学問的な演習ではなく実用的なものです。並列アルゴリズムの方が全体的にもっと多くの作業を行う可能性があります。ハードウェアを利用するだけで、一定の時間で作業を短時間で行うことができます。
私は...スイープライン法を叩くことができると信じています。左の端点がすべてx座標0を持ち、右の端点がすべてx座標1を持つn個の線分の間の交差点の数を数えることができると考えてください。これは配列内の逆位を数える古典的な問題です。だから、少なくとも特殊なケースでは、私はこの種の部分構造を探して、何らかの形でそれを利用できるはずです。 – tmyklebu
@tmyklebu、確かに、悪用可能な部分構造があれば、それを容易に活用できます。しかし、まずそれについて知る必要があります。 'O（n）'でユニットスクエアケースを簡単にチェックすることができますが、それが可能性が高いと信ずる理由がなければばかげてしまうでしょう。 （また、凸多角形の集合のような他の特殊な場合も同様です。）このような場合は「一般的なケース」ではありません。 B-Oは、実際の交差点の数を減らしてスピードアップするため、ポリゴンのコレクションをうまく処理します。 – rici
B-Oは、わずかな交点だけが存在する場合を扱います。私はまだポリゴンの束を持っているときには大まかなケースを思いつくことができます（同じ点を中心とするが、ランダムな角度で回転された正三角形を全体として描いています）。悪用可能な下位組織は...疑問点のようなものです。 :)この垂直分解アイデアを使用していると思われるChazelleの論文（「報告とカウントのセグメント交差点」）があり、私の問題のO（n 1.695）時間アルゴリズムがあると言われていますが、非実用的なデータ構造。何もないよりマシ。 – tmyklebu