立方体の箱の中に、R^3に大きな収集ポイントがあります。各点のk最近傍を見つけたいと思います。通常はkd木のようなものを使うと思いますが、この場合は周期境界条件があります。私が理解しているように、kdツリーは、スペースを1次元少ないハイパープレーンに分割して分割することで機能します。つまり、3Dでは、2Dプレーンを描画してスペースを分割します。任意のポイントについて、それは平面上、その上、またはその下のいずれかにあります。ただし、周期境界条件で空間を分割すると、点はどちらかの側にあると見なされる可能性があります。
R ^ 3の周期境界条件を持つ最近傍のリストを見つけて維持する最も効率的な方法は何ですか？
近似は十分ではなく、ポイントは一度に1つだけ移動します（N体シミュレーションではなくモンテカルロを考えてください）。
ユークリッドの場合でも、点とその最近傍は超平面の反対側にある可能性があります。kdツリーの最近傍探索のコアは、ポイントとボックスの間の距離を決定するプリミティブです。ケースに必要な唯一の変更は、ラップアラウンドの可能性を考慮に入れることです。
または、任意のメトリックで機能するカバーツリーを実装することもできます。
（完全に機能するかどうかはわかりませんが、この回答を投稿しています。直感的には正しいように見えますが、考慮していないエッジケースがある可能性があります）
周期境界条件を使用している場合は、スペースを一定のサイズの一連のブロックに分割し、それらをすべて重ね合わせたものと考えることができます。R2にいると仮定します。次に、そのブロックを9回複製し、それらをブロックの複製の3x3グリッドに配置するというオプションがあります。これを考えると、中央の正方形で単一ノードの最近傍が見つかった場合は、次のいずれかです。
言い換えると、ポイント間のユークリッド距離がモジュライ空間で対応する距離を見つけることができるように、要素を十分な回数複製するだけです。
n次元では、すべてのポイントの3 nコピーを作成する必要があります。これは多くのように聞こえますが、R3の場合は元のデータサイズの27倍にすぎません。これは確かに大幅な増加ですが、許容範囲内であれば、このトリックを使用して標準のkdツリー（または他の空間ツリー）を利用できるはずです。
お役に立てれば！（そしてこれが正しいことを願っています！）