Algorithm to find for all points in set A the nearest neighbor in set B

Question

Suppose we have two sets of points A, B, and we want to find for every point in set A its nearest neighbor in set B.

There are many good algorithms to find the nearest neighbor for one point. Is there some way to use the information we got for a_1, to more efficiently search for the nearest neighbor for a_2 or other points in the set?

I am thinking something like: use triangular inequlity to get a interval for possible distance between every point in B and new point a_2, and sort the max and min of the intervals, and then I can search only the points in B which falls in the first interval.

Answer 1

1. Find Voronoi diagram for points of set B.
2. Apply a Sweep line algorithm over points of set A and Voronoi diagram of set B. Wherever sweep line covers some point from set A, look between which edges of Voronoi diagram this point is located. This allows to determine to which face of Voronoi diagram this point belongs. Which gives the closest point from set B.

Details for step 2: Keep all edges of Voronoi diagram, currently intersected by sweep line, in some ordered container. When sweep line covers some vertex of Voronoi diagram, remove/add edges, incident to this vertex, from/to container. To look, between which edges some point is located, get successor/predecessor edges to this point in container.

Time complexity is O((M+N) log M). N = |A|, M = |B|.

Answer 2

You may benefit from reading bentleys "writing efficient programs" where he deals with a case study of the traveling salesman program. One of the savings that he recognized was that the distince between two points involved taking a square root which was expensive. Taking the square root gives you the actual distance, not taking the square root gives you a number which can be used to compare against other relative values.

I highly recommend reading the book. It will put your brain in the right place.