L1,...,Ln を平面 (IR^2) の n 個の異なる線分とする。それらはペアワイズ非交差でなければなりません。さらに距離（実数値）をｒとする。Li と Lj の (ユークリッド) 距離が r より小さいすべてのペア (i,j) を見つける問題を考えてみましょう。
関連するすべての x0 座標について n^(1/2) 線分が存在すると仮定できる場合、ランタイム O(n^(3/2)) に関する問題に対して単純で直接的なスイープライン アルゴリズムを作成しました。 x = x0 と x = x0 + r で囲まれた縦縞。
もちろん、よく知られている (またはあまり知られていない) より良いアルゴリズム (できれば O(n log(n)) アルゴリズムなど) があるかどうか、私は興味がありましたが、Google またはより具体的には適切なものを見つけることができませんでしたスタックオーバーフロー。
誰かがもっと知っていますか？