固定半径の近隣
計算幾何学において、固定半径近傍問題は最近接近傍探索問題の変形である。固定半径近傍問題では、d次元ユークリッド空間内の点の集合と固定距離 Δ が入力として与えられる。クエリ点qが与えられたとき、 qから距離 Δ 以内にあるデータ構造の点を効率的に報告するデータ構造を設計する必要がある。この問題は長年研究されてきた。Bentley (1975)は、この手法を分子構造可視化システムの一部として用いた Levinthal の 1966 年の論文を引用しており、この手法は他にも多くの応用例がある。[ 1 ]
丸めとハッシュによる解決
この問題を解決する方法の 1 つは、グリッド ポイント間の距離が目的の距離 Δ になるようにスケーリングされた整数格子にポイントを丸めることです。ハッシュ テーブルを使用すると、各入力ポイントについて、近くのグリッド ポイントにマップされている他の入力を見つけることができ、それらの丸められていない位置が実際に距離 Δ 内にあるかどうかをテストできます。この手順でテストされるポイントのペアの数と手順の時間は、次元が固定定数である場合、入力と出力を組み合わせたサイズに対して線形です。ただし、線形時間境界の比例定数は次元の関数として指数的に増加します。 [ 2 ]この方法を使用すると、線形時間で幾何学データから無差別グラフと単位ディスク グラフを構築できます。
その他の解決策
GPUを用いた最新の並列手法は、固定半径NNSの全ペアを効率的に計算できます。有限領域において、Green法[ 3 ]は、均一グリッド上でソートを行い、すべての粒子の近傍粒子をO(kn)時間で見つけることで、この問題を解決できることを示しています。ここで、kは近傍粒子の平均数に比例します。Hoetzlein法[ 4 ]は、最新のハードウェア上で、カウンティングソートとアトミック操作を用いてこれをさらに改良しました。
アプリケーション
固定半径近傍問題は、連続ラグランジュシミュレーション (平滑化粒子流体力学など)、計算幾何学、およびポイント クラウド問題 (サーフェス再構築) で発生します。
参照
参考文献
- ^ Bentley, Jon Louis (1975),固定半径近傍探索技術の概説(PDF)、技術報告書 SLAC-186 および STAN-CS-75-513、スタンフォード線形加速器センター。
- ^ Bentley, Jon L. ; Stanat, Donald F.; Williams, E. Hollins Jr. (1977)、「固定半径近傍点の探索の複雑さ」、Information Processing Letters、6 (6): 209– 212、doi : 10.1016/0020-0190(77)90070-9、MR 0489084 。
- ^ Green, Simon (2012), CUDA 粒子(PDF)
- ^ Hoetzlein, Rama (2014)、「高速固定半径最近傍法：インタラクティブ百万粒子流体」（PDF）、GPUテクノロジーカンファレンス
