Given a set P of points in the plane, design an algorithm to find the nearest neighbor for each point in P.
This problem can be solved by plane-sweep technique. We show how to find nearest neighbors to the left. Finding nearest neighbors to the right is similar. Sort all points in increasing x-coordinate and scan from left to right. For the sweep line L, we associate a set S of points in P that have nearest neighbors on L. Order the points in S in decreasing y-coordinate. We know that a circle passing through any consecutive 3 points in S, its center must lie on the right of L. Otherwise, the middl point should not be in S. Thus, for a newly processed point p, we can insert p to S properly and test whether p is closer to its neighbors in S. Then, we find the circle formed by p‘s neighbors to remove points from S. The total complexity is O(n lg n).
Klaus Hinrichs, Jurg Nievergelt, Peter Schorn, “An all-round sweep algorithm for 2-dimensional nearest-neighbor problems,” Acta Informatica 1992, Volume 29, Issue 4, pp 383-394