What would be a smart and quick way to find a pair of nearby points in two sets?

Question

For example, I have two lists of points:

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

What would be the best way to find such i and j so that a.get(i).distance(b.get(j)) minimal?

The obvious solution is brute force - calculate the distance from each point in a to each point in b , keep the pair with the shortest distance. But this algorithm is O(n^2) , which is not very good. Is there a better approach?

Answer 1

For each point in list a you can find the nearest point in list b , as described in this answer . The complexity of time is O ((M + N) log M). N = | A |, M = | B |.

Then you just look at the point in a , having the closest neighbor. The complexity of time is O (N).

Answer 2

You can put one of the lists in a quad tree or some other spatial index to quickly perform each search.

Alternatively, you can put all of your data into a database with spatial index capabilities.