Graham scan

Graham scan is a classic O(n log n) recipe for building the convex hull. The idea is to pick a definite starting corner, fan the other points out around it by angle, then walk through them once while keeping a stack of hull candidates, popping any point that would create a dent. It is like sweeping a flashlight beam around a room from one corner and tracing the silhouette: as the beam rotates, each newly lit point either continues the smooth outline or reveals that the previous point was actually a notch to be erased.

Concretely: (1) find the lowest point P0 (lowest y, breaking ties by smallest x) — it is guaranteed to be on the hull. (2) Sort all other points by the polar angle they make with P0, so you will visit them in counterclockwise order. (3) Push P0 and the first point onto a stack, then for each remaining point C, look at the top two stack points A (below) and B (top): while the triple A, B, C does NOT make a counterclockwise (left) turn — that is, while the orientation test on A, B, C is clockwise or collinear — pop B, because B is a dent. Then push C. When you finish, the stack holds the hull vertices in counterclockwise order. The popping is what carves away interior bulges. A tiny trace: with the unit square plus center, the center point gets pushed and then popped as soon as the next corner reveals it makes a right turn.

Why O(n log n): the sort dominates at O(n log n), and the scan itself is O(n) because each point is pushed once and popped at most once, so the total push/pop work is linear (an amortized argument). Graham scan is exact when implemented with the integer orientation test, but it has two honest pitfalls: collinear points on the hull edges need a tie-breaking convention in the angle sort (decide whether to keep or drop them), and the polar-angle sort is where subtle bugs hide. For those reasons many practitioners prefer Andrew's monotone chain, which sorts by coordinate instead of angle and is easier to get right.