Given a bunch of points, how can we figure out which two points are closest to each other? We could compare all of the points and choose the pair with the minimum distance, but that’s a lot of work.

Below the cut, I try to explain a better algorithm to find the closest pair of points. This algorithm and its explanation are all over the Internet, so surely one more explanation won’t hurt. Besides, I think mines has the most pictures in it. :)

Viewer Advisory: Some graphs and technical language.

Continue reading