CODEWITHSUNDEEP
javaalgorithmgeometrypoint
Rogach
Rogach

Reputation: 27260

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

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)) is minimal?

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

Upvotes: 4

Views: 752

Answers (2)

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

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

Then you just search the point in a, having the nearest neighbor. Time complexity is O(N).

Upvotes: 3

Albin Sunnanbo
Albin Sunnanbo

Reputation: 47068

You can put one of the lists in a quad tree or some other spatial index to make each lookup fast.

As an alternative you could put all your data in a database with spatial index capabilites.

Upvotes: 3

Related Questions