Points on a Plane

Looking for actual 2D planes with points on them? Scroll down!

Like snakes, points on a plane can also present a huge problem. I never thought this was the case, until last week when we were presented with the problem of finding the closest pair of points in a set of points on a plane...using a O(nlogn) algorithm.

My experience during that lecture was like standing on quicksand: I was breathing easily at first, but by the end of the hour, I was chin deep in sand and it was all I could do to not throw in the towel.

After a long break from my horrid, sandy experience in lecture, I resolved to understand the algorithm for finding the closest pair of points. My sparse, confusing notes were barely helpful, but they did remind me what my problem was: Why are we comparing points within that square? Why that many points, and no more? Why could we technically compare with even fewer points within that box? I only understood up to our calculation of the width of the middle section. Beyond that, I was lost.

At this point, I decided the best use of my time was to seek Google's help. I found two videos from Coursera's algorithms class on exactly this problem very helpful; they explained the problem quite clearly, and it helped that I could pause and rewind any confusing sections.

Waking up the next day, I had pretty much grasped the algorithm. I still had one problem though: In our lecture and the Coursera videos, the set of points in the middle section were each in its own little box. I saw how this aided the explanation, but I wasn't sure what this was a representation of. Was it how the computer was seeing it (a 2D array)? Was it just for us to see? But if that's the case, points are on lines, not grids. How would these points be represented on the familiar Cartesian plane?

So I started drawing, plotting points on a grid and coming up with various point configurations. Being able to visualize what the algorithm was actually doing was really helpful. (If you can't already tell, I like pictures.)

I like to think that the algorithm is firmly in my grasp now. Given the sheer trouble it took to understand this problem, I present my take on this algorithm, in hopes that it'll help others understand it too. (If there are any errors, please correct me!)

EDIT: I realize that the pictures are kinda small here. The pictures can only be so wide with this layout. My other blog has a version where the text is a bit easier to read.

Today: Toronto, Canada
Drawing that took more time than expected. Consequently, I've no time to travel. It's also not safe to travel during a hurricane. So I'm just staying home this time.