algorithm - 平面内の最も近いペアの倍数の決定

Question

以下に概説するスイープ アルゴリズムを使用して平面内の頂点の最も近いペアを決定する場合、追加の実行なしで複数のペアを決定することは可能ですか?

1. ポイントを x 座標に従って並べ替えます。
2. 垂直線 x=xmid によって、点のセットを 2 つの等しいサイズのサブセットに分割します。左サブセットと右サブセットで問題を再帰的に解きます。これにより、左側と右側の最小距離 dLmin と dRmin がそれぞれ得られます。
3. 1 つのポイントが分割垂直線の左側にあり、もう 1 つのポイントが右側にあるポイントのペアのセットの中から最小距離 dLRmin を見つけます。
4. 最終的な答えは、dLmin、dRmin、および dLRmin の最小値です。

Answer 1

等しい最も近いペアを別のリストに保存する必要があります。

2 つの距離を比較するときは常に、最短距離と別のリストの距離を比較する必要があります。

短い場合は、リストを空にします。

等しい場合は、リストに追加します (おそらく両方のペア)。

一定時間ストアを使用すると、アルゴリズムの複雑さが低下することはありません。