半径Rが固定され、高さ、幅、長さが既知の空間の場合、その空間に3次元座標を持つ点のリストNが、固定内のすべての点を見つける効率的なアルゴリズムを探しています。グリッド上の任意の点の半径R。このクエリはさまざまなポイントで何度も実行されるため、迅速なクエリと引き換えに、費用のかかる前処理/並べ替えの手順を実行する価値がある場合があります。これは、私が取り組んでいるアプリケーションのボトルネックのステップであるため、いつでも切断できると便利です。
私がこれまでに試したこと：
-素朴なアルゴリズム、すべてのポイントを反復し、距離を計算します
-スペースを長さRの立方体のグリッドに分割し、これらにポイントを配置します。そうすれば、各ポイントについて、すぐ隣のバケットにクエリを実行するだけで済みます。これにより、大幅なスピードアップが実現します
-ヒューリスティックとしてマンハッタン距離を使用してみました。つまり、バケット内で、任意のポイントまでの距離を計算する前に、マンハッタン距離を使用して、半径R内に収まらない可能性のあるもの（つまり、マンハッタン距離が<= sqrt（3）* Rの場合）を除外します。 ）。乗算ではなく加算が必要なため、これでスピードアップできると思いましたが、実際にはプログラムの速度が少し遅くなりました。
編集：距離を比較するために、平方根関数を使用する必要をなくすために、距離の2乗を使用します。
明らかに、これをどれだけスピードアップできるかにはある程度の制限がありますが、今試してみるための提案を使用することができます。
おそらくアルゴリズムレベルで問題になるわけではありませんが、私はCで作業しています。