Make Pythagoras Proud

I am interested in a somewhat lesser known branch of algorithms. Geometric algorithms are algorithms that (duh) deal with geometry. In all of my schooling the only algorithm that I was ever exposed to from this class was Quick Hull. Which calculates the convex hull of a set of points (Go read that if you don't know what a convex hull is otherwise this probably won't make sense).

Quick Hull is optimal (in the big-O sense) for calculating the convex hull. It turns out that that the optimal class for such an algorithm is O(n log n) just like comparison based sorting! Why? Because we can use a convex hull to sort a set of points!

How you ask? Well first you should know that the hull algorithms produces edges of the polygon in sorted order. If you have a list of unique numbers to be sorted L[N]. First make a list of points P[N] = new point(L[i], L[i]^2) and make the convex hull of the point cloud. If you start from the lowest coordinate the sorted order of points will just be a traversal of the generated polygon (which direction depends on how you constructed it but its traditionally counter-clockwise).

So that means that if we could convex hull faster then O(n log n) we could sort faster too! It often amazes me how results from such disparate parts of computer science can be related so closely. Further it turns out that if the points are pre-sorted in certain ways you can build the hull in O(n). Which means most of the work done by the general hull algorithms is in sorting the edges.

Now there are hull algorithms that are "output sensitive". The best of those produce a hull in O(nh) with h being the number of points that form the hull. h is generally much smaller then n, because for random data most of the points in the set get thrown away when it is determined they are inside the hull. But we contrived the situation such that every point is on the hull (h == n) so those algorithms would be slower.

Convex Hulls are by no means the only algorithms in Computational Geometry (though they are one of the most important). Some of the algorithms have application in areas that you would never think of. So if you feel inclined I recommend you check Computational Geometry out.