これが重複している可能性があることはわかっていますが、「最も近いポイントのペア」アルゴリズムのバリエーションのようです。
単位正方形内のN 個の点 (x, y)のセットと距離dが与えられた場合、それらの間の距離が最大でdになるすべての点のペアを見つけます。
Nが大きい場合、ブルート フォース法はオプションではありません。「掃引法」と「分割統治法」以外に、もっと簡単な解決策はありますか? これらのポイントのペアは、無向グラフのエッジであり、それをトラバースして接続されているかどうかを判断する必要があります (これは既に DFS を使用して行いましたが、N = 100 万の場合は終了しません!)。
疑似コード、コメント、アイデアは大歓迎です。ありがとう!
編集：私はSedgewickの本でこれを見つけました（私は今コードを見ています）：
プログラム 3.18 は、リンクされたリストの 2 次元配列を使用して、N が十分に大きい場合、プログラム 3.7 の実行時間を約 1/d2 倍改善します。単位正方形を同じサイズの小さな正方形のグリッドに分割します。次に、各正方形について、その正方形に該当するすべてのポイントのリンク リストを作成します。2 次元配列は、特定のポイントに近いポイントのセットにすぐにアクセスする機能を提供します。リンクされたリストは、各グリッドの正方形にいくつのポイントが入るかを事前に知る必要なく、ポイントが入る可能性のあるポイントを格納する柔軟性を提供します。