Sketch · 2026-07-24
Convex hull, by monotone chain.
The convex hull of a set of points is the smallest convex polygon that contains all of them. Stretch a rubber band around a scattering of pins on a board and let it snap: the shape it takes is the hull. Andrew's monotone chain finds it in O(n log n) with a single sort and two passes.
Click to add a point. Points get scattered, the hull re-wraps.
The algorithm
Sort the points by x, breaking ties by y. Walk them left to right. Keep a stack; before pushing the next point, pop the top as long as the last three points make a right turn or a colinear triple. That stack, when the walk finishes, holds the lower hull. Repeat right to left for the upper hull, using the same right-turn test. Concatenate the two chains, drop the duplicate endpoints, and the hull is closed.
The right-turn test itself is one cross product. For three successive points a, b, c the sign of (b.x - a.x)(c.y - a.y) minus (b.y - a.y)(c.x - a.x) tells you the orientation: positive is a left turn, negative a right turn, zero a straight line. The whole procedure fits in about twenty lines and does not need trigonometry.
Why the sweep is enough
The leftmost and rightmost points are always on the hull. Every point lies either above the line connecting them, below it, or on it. Points above end up on the upper chain, points below on the lower, and one sorted pass over each half is enough because each candidate can be visited at most twice: once when pushed, once when popped. That is where the linear amortized bound comes from. The sort dominates the total cost.
Where it shows up
Collision detection engines use the hull of a mesh as a first broad-phase test. Route planners use hulls to prune candidate waypoints. Computer vision uses them to bound a segmented silhouette. In machine learning, the convex hull of a training set marks the region where a linear classifier can still be trusted; anything outside is extrapolation. The same monotone chain generalises to higher dimensions as the gift-wrapping family of algorithms.
Sources
- Andrew, A. M. (1979). Another Efficient Algorithm for Convex Hulls in Two Dimensions. Information Processing Letters, 9(5), 216–219. The paper that introduced the monotone chain method used here.
- Graham, R. L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters, 1(4), 132–133. The earlier scan by polar angle around a pivot, replaced by Andrew's lexicographic sort.
- de Berg, M., Cheong, O., van Kreveld, M. and Overmars, M. (2008). Computational Geometry: Algorithms and Applications (3rd ed.), chapter 1. The standard textbook treatment, with correctness proofs.