# Graham's Scan

Given a set of points on the plane, Graham's scan computes their convex hull. The algorithm works in three phases:
1. Find an extreme point. This point will be the pivot, is guaranteed to be on the hull, and is chosen to be the point with largest y coordinate.
2. Sort the points in order of increasing angle about the pivot. We end up with a star-shaped polygon (one in which one special point, in this case the pivot, can "see" the whole polygon).
3. Build the hull, by marching around the star-shaped poly, adding edges when we make a left turn, and back-tracking when we make a right turn.
Here's a demonstration of Graham's scan. It finds the convex hull of 30 points randomly positioned on the plane. Click on "Run" to start the demo.

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

Here we see an example where the points are in convex position, ie, they are the vertices of a convex polygon. In this case, the algorithm makes no right turns, and hence never has to back-track.

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

Alejo Hausner, CS Department, Princeton University