Points on a plane

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.

OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE! OH GOD there are snakes AND points on a plane! I CAN'T COPE!
  • Ian

    Hi,
    I have been reading your blog for a while. Just wonder what tools you use for drawing those diagrams. Thanks

    • http://superchlorine.com/ cL

      Thanks for reading my stuff! It’s always nice to know I’m not just talking to myself all the time.

      I usually use Inkscape to draw. It’s a free open-source program you can download here. You can think of it as a simpler version of Adobe Illustrator, but it’s powerful enough for what I need to do.