問題：
3Dユークリッド空間にはn個の頂点のセットがあり、これらの頂点は偶数個あります。
近接度に基づいてペアリングしたいと思います。つまり、各ペアの頂点が可能な限り接近している頂点ペアのセットを見つけられるようにする必要があります。
これを行う際に、他のペアの頂点間の近接性をできるだけ犠牲にすることを最小限に抑えたいと考えています。
私は最適な解決策を探していません（厳密に存在する/実行できる場合でも）、比較的迅速に計算できる合理的な解決策を探しています。
比較的ひどい強引なアプローチでは、頂点を選択し、残りの部分をループして最も近い隣人を見つけ、残りがなくなるまで繰り返します。もちろん、リストの終わりに近づくにつれて、最も近い頂点が非常に遠くなる可能性がありますが、それが唯一の選択肢であるため、上記の3番目のポイントでこれはひどく失敗する可能性があります。
あなたは最適な解決策を探していないので、ここにあなたが考えるかもしれないヒューリスティックがあります。
各ポイントpについて、2つのポイントを計算します。それぞれpに最も近いおよび最も遠い最も近いネイバーと最も遠いネイバーです。ここで、qを最も遠い隣の点とします（qは入力の極値点です）。qを最も近い近傍と照合し、両方を削除して、残りのポイントの照合を再帰的に計算します。
これは確かに最適ではありませんが、小さな入力セットではかなりうまくいくようです。最適な解が必要な場合は、ユークリッドマッチング問題について読む必要があります。
この種の問題（特にnが大きい場合）の一般的なアプローチは、kdツリーや八分木などの空間インデックス構造を事前に計算し、それを利用して最近傍の検索を実行することです。オクトツリーのノードを介して、使用可能なポイントがビンに入れられるため、それらが相互に近接していることを確認できます。また、比較の数を最小限に抑えます。
オクトツリーを使用した実装のスケッチ：バウンディングボックスを格納するNodeクラスが必要です。派生したLeafNodeクラスは、最大値（k = 20など）までの少数のポイントを格納します。これらのポイントは、挿入関数で追加されます。派生したNonLeafNodeクラスは、8つのサブノード（LeafとNonLeafNodeの両方の場合があります）への参照を格納します。
ツリーはルートノードで表され、すべての挿入とクエリはここから始まります。ツリーは、LeafNodeに挿入された最初のk個のポイントから開始して構築されます。k + 1番目のポイントが挿入されると、バウンディングボックスは8つのサブボックスに分割され、含まれているポイントがそれらにソートされます。現在のLeafNodeは、8つのサブノードを持つ1つのNonLeafNodeに置き換えられます。これは、すべてのポイントがツリーに含まれるまで繰り返されます。
最近傍検索の場合、ツリーはバウンディングボックスと比較してルートノードから開始してトラバースされます。クエリポイントがノードのバウンディングボックス内にある場合、トラバーサルはそのノードに入ります。最も近い候補を見つけた場合は、八分木内の隣接ノードも確認する必要があることに注意してください。
kdtreeの実装については、ウィキペディアのページを確認してください。非常にわかりやすく見えます。