0

これを解決する方法については、ウィキペディアのエントリを見ています。それは5つのステップをリストします

1.x座標に沿ってポイントを並べ替える

2.点のセットを垂直線 x = xmid で 2 つの等しいサイズのサブセットに分割します。

3.左部分集合と右部分集合で再帰的に問題を解きます。これにより、左側と右側の最小距離 dLmin と dRmin がそれぞれ得られます。

4.1 つの点が分割垂直線の左側にあり、2 番目の点が右側にある点のペアの間で最小距離 dLRmin を見つけます。

5.最終的な答えは、dLmin、dRmin、dLRmin の最小値です。

4番目のステップが理解できません。線の右側の点と比較する線の左側の点を選択するにはどうすればよいですか。すべてのポイントを比較する必要はないことは承知していますが、比較するポイントをどのように選択すればよいかわかりません。リンクを送信しないでください。検索し、多数のリンクにアクセスしましたが、ステップ 4 を理解するのに役立つ説明が見つかりませんでした。

ありがとう

アーロン

4

1 に答える 1

2

あなたの質問に対する答えは、ウィキペディアの記事の次の段落にありました。

ステップ 4 は線形時間で実行できることがわかります。繰り返しますが、素朴なアプローチでは、すべての左右のペアの距離を計算する必要があります。つまり、二次時間で計算します。重要な観察結果は、ポイント セットの次のスパース プロパティに基づいています。最も近い点のペアが dist = min(dLmin,dRmin) よりも離れていないことは既にわかっています。したがって、分割線の左側の各点 p について、図に示すように、分割線の右側にある次元 (dist、2 * dist) の長方形内にある点までの距離を比較する必要があります。さらに、この長方形には、少なくとも dRmin のペアワイズ距離を持つ最大 6 つのポイントを含めることができます。したがって、ステップ 4 で最大 6n の左右距離を計算すれば十分です。

彼らがすでに持っているよりも明確に説明できるとは思いませんが、アルゴリズムのこのステップについて具体的な質問はありますか?

于 2011-04-24T23:39:08.763 に答える