Given a set *P* of points in the plane, design an algorithm to find the nearest neighbor for each point in *P*.

**Solution**:

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*).

Reference: Stackoverflow

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