the convex-hull lower bound

It is natural to ask: could some clever trick compute the convex hull faster than the O(n log n) of Graham scan and monotone chain? The convex-hull lower bound answers no — at least, not by any comparison-based method, and not in the worst case. It proves a hard floor of Omega(n log n) on the time to compute a hull, by showing that if you could find hulls quickly you could also sort quickly, and sorting itself cannot be done faster than n log n by comparisons.

The argument is a reduction from sorting, and it is elegantly simple. Suppose you want to sort n real numbers x1, ..., xn. Map each number xi to the point (xi, xi^2), which lands it on the parabola y = x^2. Every point on a parabola is a vertex of the convex hull of any set of such points (the parabola curves only one way, so no point is ever inside the others). Now compute the convex hull of these n points. The hull, read off in order around its boundary, lists the points sorted by their x-coordinate — which is exactly the sorted order of the original numbers. So a hull algorithm, plus O(n) work to build the points and read them back, sorts n numbers. Since comparison sorting needs Omega(n log n), so must any comparison-based hull algorithm.

This is a textbook example of using a reduction to prove a lower bound, and it carries two honest lessons. First, the bound is for the comparison/algebraic-decision-tree model; it does not forbid faster methods that exploit special structure, such as integer coordinates in a bounded range, where bucket-style tricks can beat n log n. Second, a reduction from A to B shows B is at least as hard as A — here hull-finding is at least as hard as sorting — it does NOT say hull-finding is easy. The bound matches the O(n log n) upper bounds of Graham scan and monotone chain, so for general inputs those algorithms are optimal.