c++ - C ++の2点間の最小距離

Question

m の場所 (x、y 座標) が与えられます。

与えられたポイント P(x,y) に最も近い場所を見つけるという n 個のリクエストがあります。(最小ユークリッド距離)

O(n*m) 以下でこの問題を解決するにはどうすればよいですか。ここで、n はリクエストの数、m は場所の数です。二乗ユークリッド距離を使用できますが、それでも n*m です。

Answer 1

kd-treeを試してください。高性能ライブラリの実装はここにあります。

注：高次元用に最適化されたおおよその最近傍探索を示しています。これは、アプリケーションにとってやややり過ぎかもしれません。

編集：

2d kdツリーの場合、ビルド時間はO（m * log（m））になり、クエリ時間はO（n * sqrt（m））になります。クエリの数nがlog（m）を超える場合、これは単純なソリューションに対する正味の勝利になるはずです。

ライブラリは、実装する必要がないことを意味するため、複雑さは問題になりません。

高次元の非常に高速なクエリに一般化する場合は、局所性鋭敏型ハッシュを確認してください。

Answer 2

面白い。nの影響を減らすために、各リクエストの結果を見つけて処理するときに保存するのが役立つのではないかと思います。巧妙な結果テーブルは、後続のリクエストを解決する際に sqrt（x ² + y ^{2 ）を計算する必要性を短縮する可能性があります。}

Answer 3

最近傍問題、え？これらの場合、 Robert Sedgewick Std Bookが非常に役立つことがわかりました。Nearest Neighbor Searchについても説明しています。