Andrew's monotone chain

Andrew's monotone chain is an O(n log n) convex-hull algorithm that many people reach for instead of Graham scan, because it replaces the fiddly polar-angle sort with a plain sort by coordinate. The picture: lay all your points out and sort them left to right (by x, ties by y). Now sweep across them building the bottom edge of the hull, then sweep back building the top edge, and glue the two chains into a loop. Sorting by x once and going through the points twice is simpler and more numerically robust than sorting by angle around a pivot.

Here is how a single sweep builds the lower hull. Process points left to right, maintaining a stack. For each new point C, while the top two stack points A, B together with C do NOT make a counterclockwise turn (orientation A,B,C is clockwise or collinear), pop B; then push C. This is exactly the Graham-scan popping rule, but applied to x-sorted points, so it traces the lower boundary as a sequence of left turns. Then do the same sweep right to left to build the upper hull. Concatenate the lower chain and the upper chain (dropping the two shared endpoints so corners are not duplicated) and you have the full hull in counterclockwise order. A trace on the unit square plus center: the lower sweep keeps (0,0),(4,0),(4,4) and pops the center; the upper sweep keeps (4,4),(0,4),(0,0); joined, the hull is the four corners.

Its cost is O(n log n) dominated by the single coordinate sort; each sweep is O(n) by the same amortized push-once, pop-at-most-once argument as Graham scan. Compared with Graham scan it avoids computing or comparing angles entirely, so it sidesteps a whole class of precision and tie-breaking headaches and is the version most competitive programmers memorize. The same honest caveat applies: how you treat collinear points on a hull edge (keep them all, or only the extreme endpoints) is a deliberate choice you must encode in whether the popping condition rejects collinear triples.