Graham Scan (Convex Hull)

Ronald Graham, 1972

Published by Ronald Graham in 1972, the Graham scan finds the convex hull -- the smallest convex polygon enclosing all points. It picks the lowest point as an anchor, sorts the rest by polar angle, then scans through the sorted points while maintaining a stack: if a turn goes clockwise (wrong direction), points are popped off. The visualization shows points with the anchor in coral, hull vertices in teal, the current candidate in gold, and rejected points briefly flashing before fading.