接続された線分のグループのカウンタの数

Question

私は次の問題を解決しようとしています。開始点と終了点のある線分がたくさんあるとします。それらはすべて水平または垂直です。私は、与えられたセグメントのセット内のコンポーネントの数を数えるためのアルゴリズムを考え出しています。コンポーネントとは、各セグメントが少なくとも1つの他のセグメントと交差する線分のセットです（つまり、任意のセグメントの任意の点から他のセグメントの任意の点に到達することができます）。明らかなO（N^2）ソリューションよりもこれを行うことは可能ですか？

Answer 1

ラインスイープアルゴリズム(1)(2)を使用して、交差を探すことができます。
これらの交差を使用して、セグメントのクラスタをunion-find algorithmにします。

交差カウントが高い場合（約O（N^2））、このアプローチは2次的である可能性があることに注意してください。