分割統治アルゴリズムが 2 より大きい次元でどのように機能するか、特に 2 つのサブ問題間で最も近い点のペアを見つける方法について頭を悩ませています。
軸d上の 2 つの間の分割の距離内にある点のみを考慮する必要があることはわかっています。x
3 次元の場合、各点を他の 15 点のみと比較する必要があることはわかっています。
私が理解できないのは、それらの 15 点を選択する方法です。2 番目のケースでは、単純に値をy値でソートし、順番に調べます。y ただし、3D の場合、各ポイントは、軸と 軸の両方で最も近い 15 個のポイントと比較する必要がありますz。最悪の場合を除いて、これらの 15 ポイントが何であるかを判断する方法を見つけることができないようですO(n^2)...
ここで何が欠けていますか？
簡単な解決策は、すべてのポイントを使用して octree または kd ツリーを作成し、それを使用してすべてのポイントの最も近いポイントを見つけることです。これは、平均的なケースでは O(N*log N) です。
平均的なケースでは O(N) であると私が考えるより高速なソリューションは、次のアイデアを考慮して実装できます。
スペースを半分に分割すると (たとえば、軸に沿った平面で)、点が A と B の 2 つのサブセットに分割され、最も近い 2 つの点が両方とも A に、両方が B に、または 1 つが A に、もう 1 つが A にある可能性があります。 B.
したがって、3D ボックスのペアのキューを作成し、それらの間の最小距離で並べ替えてから、次のようにする必要があります。
1) キューから最初のボックスのペアを選択します
2) 両方のボックスが同じボックス A の場合、それを 2 つのボックス B と C に半分に分割し、(B, B)、(C, C)、(B, C) のペアをキューに入れます。
3) それらが異なる場合 (A、B)、最大のもの (たとえば B) を半分に分割してボックス C と D を取得し、ペア (A、C) と (A、D) をキューにプッシュします。
4) 繰り返します。
また、ボックスのペア内のポイントの数があるしきい値を下回った場合、ブルート フォースを使用して最も近いポイントのペアを見つけることができます。
上部のペアの 2 つのボックス間の距離が、これまでに検出された最小距離よりも大きくなると、検索が停止します。