問題タブ [line-segment]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 距離が特定の境界より小さいすべての線分のペアを見つける
L1,...,Ln を平面 (IR^2) の n 個の異なる線分とする。それらはペアワイズ非交差でなければなりません。さらに距離(実数値)をrとする。Li と Lj の (ユークリッド) 距離が r より小さいすべてのペア (i,j) を見つける問題を考えてみましょう。
関連するすべての x0 座標について n^(1/2) 線分が存在すると仮定できる場合、ランタイム O(n^(3/2)) に関する問題に対して単純で直接的なスイープライン アルゴリズムを作成しました。 x = x0 と x = x0 + r で囲まれた縦縞。
もちろん、よく知られている (またはあまり知られていない) より良いアルゴリズム (できれば O(n log(n)) アルゴリズムなど) があるかどうか、私は興味がありましたが、Google またはより具体的には適切なものを見つけることができませんでしたスタックオーバーフロー。
誰かがもっと知っていますか?