The smallest enclosing shape
The convex hull of a set of points is the smallest convex polygon that contains them all. Imagine stretching a rubber band around nails on a board and letting it snap tight; the band traces the hull. Graham scan builds it efficiently using the orientation test.
The procedure
The scan has two phases:
- Sort the points by angle around a chosen anchor, usually the lowest point.
- Walk the sorted points, maintaining a stack of hull candidates.
While adding each new point, you check the orientation of the last two stack points with the new one. If they make a right turn, the middle point is inside the hull, so you pop it. You keep popping until the last three make a left turn, then push the new point.
Why the walk is cheap
Each point is pushed once and popped at most once, so the walk is linear after sorting. The sort dominates the cost. The orientation test does all the geometric reasoning, which keeps the logic exact for integer inputs and free of tricky angle arithmetic during the walk.
Key idea
Graham scan sorts points around an anchor, then pops every point that makes a right turn so the surviving stack is the convex hull.