The Graham Scan computes the convex hull of a set of points in 2D.

It sorts all the input points by angle relative to the top-most point, and then adds points from the sorted list to the hull, until it finds that adding the next (sorted) point will cause the current point to be non-convex, whereupon it backtracks until it finds a suitably convex point and continues. The cost of the algorithm is dominated by the O(n log n) time to sort.

Click the applet to generate a new set of points and watch the algorithm again.