What a convex hull is
The convex hull of a set of points is the smallest convex polygon that contains them all, like a rubber band snapped around nails. Graham scan builds it efficiently.
Choosing the pivot and sorting
Pick the point with the lowest y coordinate, breaking ties by x, as the pivot. It is guaranteed to be on the hull. Then sort the remaining points by the polar angle they make with the pivot.
- Ties in angle are broken by distance from the pivot.
- The sort dominates the running time.
The scanning stack
Walk the sorted points while maintaining a stack of hull vertices. For each new point, check the orientation of the top two stack points with it.
- While the turn is a right turn or collinear, pop the top, because it cannot be on the hull.
- Then push the new point.
After processing every point the stack holds the hull in counterclockwise order.
Cost and care
The angular sort sets the overall cost, and the linear scan after it is cheap because each point is pushed and popped at most once. Collinear points need a consistent tie rule to avoid spurious vertices.
Key idea
Graham scan anchors on the lowest point, sorts the rest by polar angle, then sweeps once with a stack that pops every right turn, leaving exactly the convex boundary in order.