java - 2 つのセットで最も近いポイントのペアを見つけるためのスマートで迅速な方法は何でしょうか?

Question

たとえば、ポイントのリストが 2 つあります。

List<Point2D> a;
List<Point2D> b;

iそのようなとを見つけるための最良の方法は何でしょうか?jそれa.get(i).distance(b.get(j))は最小限です?

明らかな解決策は力ずくです。 の各ポイントから の各ポイントまでの距離を計算aしb、ペアを最短距離に保ちます。しかし、このアルゴリズムはO(n^2)、良くありません。より良いアプローチはありますか？

Answer 1

リストの1つをクワッドツリーまたはその他の空間インデックスに配置して、各ルックアップを高速化できます。

別の方法として、すべてのデータを空間インデックス機能を備えたデータベースに配置することもできます。

Answer 2

この回答で説明されているように、リストのすべてのポイントについて、リストaから最も近いポイントを見つけることができます。時間計算量は O((M+N) log M) です。N = |A|、M = |B|。b

a次に、最も近い近傍を持つ点を で検索します。時間計算量は O(N) です。