6

http://en.wikipedia.org/wiki/Closest_pair_of_points_problem で、残りの半分のポイントに最も近い最大6つのポイントについて言及していることがわかります。これは、以下のグラフで表すことができます 。 ここに画像の説明を入力してください

私の質問は、ポイントP1とポイントP2についてですが、赤いポイントまでの距離はsqrt（2）* dを超えますが、なぜそれがソリューションの一部なのですか？Pに最も近いのは最大6ポイントではなく、最大4ポイントではないのはなぜですか？ありがとう。

4

3 に答える 3

9

P1とP2はソリューションの一部ではありませんが、アルゴリズムがボックス内のすべてのポイントを検査し、P1とP2がボックス内にあるため、ソリューションに向かう途中で検査する必要があります。

仮説により、図の右半分の点間の最小距離はdであるため、 Qのような点は存在できないことに注意してください。

追加するために編集：あなたはウィキペディアの記事がこのような主張をしていると思うようです：

  • Pの距離d内にある線の右側に最大6つのポイントが存在する場合があります。

この主張は誤りです。しかし、記事はそのような主張をしていません。代わりに、2つの別個の主張を行い、どちらも真実です。

  1. Pの距離d内にある線の右側のすべての点は、ボックスの内側にあります。
  2. ボックスには最大6つのポイントが含まれる場合があります。

于 2012-09-15T12:30:24.680 に答える
3

右のdx2d長方形にあることができるポイントの最大数のみをカウントしています。任意の2点は、最小距離dを持つように制約されているため、図に示すように、この制約を満たしながら、長方形内に最大6つの点を配置​​できます。

Pからdの距離内にある右側の点はすべて、Pを中心とし、半径がdである円の円形セグメント内にある必要があることに注意してください。このセグメントには最大で4つのポイントがあります。ただし、セグメント内のポイント数を見つけることは、長方形内のポイント数を見つけることよりも複雑です。したがって、代わりに長方形を使用し、最大2つの追加ポイントを検索する必要があるという追加コストが発生します。

于 2012-09-15T12:27:48.427 に答える
2

境界は、複雑さの推定にのみ重要です。コード的には、距離dRmin内で上下にスキャンするだけです。ここでの限界は、このようなスキャンごとに最大6つのポイントが表示されることを示しており、これがO（1）になります。

于 2012-09-15T12:37:46.357 に答える