Every other entry in this category answers "what is the boundary of this point set" — Graham
Scan, Jarvis March, Monotone Chain, Quickhull, Chan's Algorithm, and Divide-and-Conquer Convex Hull
all build the same convex hull by different routes, and Rotating
Calipers asks a different question about a hull that already exists (its diameter). This page
asks a third kind of question, with no polygon or point set anywhere in sight: given a handful of
linear functions y = mx + b, which one is largest at a given x? Checking
every function directly costs O(n) per query. The Convex Hull Trick
answers repeated queries like this in O(1) amortized time each, after an
O(n) build, by keeping only the lines that are ever the best answer for some
x and discarding the rest — and the surviving lines, plotted together, trace out the
upper edge of a convex shape. That's not a coincidence or a name chosen for flavor: when the
functions are ordered by slope, the one that's largest at each x changes in the same
convex order a physical hull's vertices do, which is why the "is this one ever needed" test below
reuses the identical logic a hull-building algorithm uses to throw away an interior point.
The technique goes by Convex Hull Trick (CHT) in competitive programming, where
it's almost always reached for to speed up a dynamic program whose transition is a minimum or
maximum over a growing set of linear cost functions — turning an O(n²) DP into
O(n log n) or O(n) without changing what it computes, only how fast. The
version built below assumes the lines are known ahead of time and inserted in decreasing-slope
order, answering a stream of non-decreasing queries with a deque and a single forward-moving
pointer — the classic, cheapest form. When lines have to be inserted in arbitrary order, or queries
jump around unpredictably, the usual answer is a different structure entirely, a Li Chao Tree (introduced by Li Chao
at ZJOI 2012) — a segment tree over the x-axis
that pays O(log n) per insert and per query no matter what order either arrives in.
That's a genuinely different data structure, not a variant of the deque below.
A publisher is comparing five royalty contracts before choosing one. Contract
X pays $m per copy sold plus a one-time signing bonus
$b — total payout m·x + b for a print run of x copies. Press
Step or Run to watch the five contracts get inserted highest-
royalty-first, then a run of sales projections get queried low-to-high. The checkbox reruns the
exact same code on the same five contracts in their original, not royalty-sorted order —
see Pitfalls for what that breaks.
Insert lines in decreasing-slope order and keep them in a deque. When a new line
C arrives, look at the last two lines already kept, A (second-to-
last) and B (last). B is only ever the best answer somewhere if
there's a window of x where it beats both A (true left of where
A and B cross) and C (true right of where
B and C would cross) at the same time. That window turns out to
exist exactly when A and C's own crossing point falls to the
left of A and B's — so the test only ever needs to compare
A against C, never against the B-C
crossing directly. If A and C cross at that same point or later
instead, the window is gone: B is never the maximum for any x, ever,
no matter what gets inserted after C, and it's popped for good before
C is pushed. On this page's
five contracts, that's exactly what happens to Cedar the instant
Delta is inserted. Cedar only ever beats Bramble below 2,000 copies, and only ever
beats Delta below 6,000 copies — so its only possible window to be the best deal anywhere is below
2,000 copies. But Delta already beats Cedar everywhere in that whole range (at 1,000 copies, Delta
pays $28,000 against Cedar's $23,000), so Cedar is dominated across its
entire would-be window before that window even opens. It's popped for good the moment Delta
arrives, without a single sales projection ever being run.
The query side leans on the same convexity. Once the deque only holds lines that are each best
somewhere, those somewheres are ordered along the x-axis exactly like the deque itself — the
steepest line (best for large x) at one end, the shallowest (best for very small
x) at the other. So for a single pointer walking a non-decreasing sequence of
query x values, the right answer never sits behind where the pointer already is; it
only ever sits at the pointer's current line or further toward the steep end. The pointer starts at
the shallow end and only advances, never backtracks, so across a whole run of m
monotonic queries against n kept lines it makes at most n total moves —
O(1) amortized per query, not per-query O(n) or even
O(log n). Queries that don't arrive in sorted order give up that amortized bound but
keep correctness by binary-searching the deque's own crossing points instead, at
O(log n) per query — still far cheaper than checking every line.
// lines must be added in decreasing-slope order.
function makeConvexHullTrick() {
const lines = []; // kept lines, decreasing slope, each a genuine winner somewhere
let ptr = -1; // pointer for the monotonic-query fast path
function evalAt(line, x) { return line.m * x + line.b; }
// True if b (the middle of three consecutive decreasing-slope lines) is never the
// maximum for any x -- a and c's own crossing already happens at or before a and b's.
function unnecessary(a, b, c) {
return (c.b - a.b) * (a.m - b.m) >= (b.b - a.b) * (a.m - c.m);
}
function add(m, b) {
const next = { m, b };
while (lines.length >= 2 &&
unnecessary(lines[lines.length - 2], lines[lines.length - 1], next)) {
lines.pop();
}
lines.push(next);
}
// Assumes x is >= every x passed to the previous call -- a non-decreasing query stream.
function queryMonotonic(x) {
if (ptr < 0 || ptr >= lines.length) ptr = lines.length - 1;
while (ptr > 0 && evalAt(lines[ptr - 1], x) >= evalAt(lines[ptr], x)) ptr--;
return evalAt(lines[ptr], x);
}
// No ordering assumption on x -- binary search over the deque's own crossing points.
function queryAny(x) {
let lo = 0, hi = lines.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (evalAt(lines[mid + 1], x) >= evalAt(lines[mid], x)) lo = mid + 1; else hi = mid;
}
return evalAt(lines[lo], x);
}
return { add, queryMonotonic, queryAny, lines };
}Unsorted insertion order doesn't crash — it silently answers wrong. The
unnecessary() test only proves a line can never win under the guarantee that slopes
arrive decreasing; feed it the same five contracts in their original order (Bramble, Nova, Ember,
Cedar, Delta — nothing shuffled for effect, that's the order they were pitched in) and the exact
same code runs without any error. Checked directly on this page's own five sales projections
(500, 2,000, 5,000, 9,500, and 12,000 copies): 4 of the 5 come back wrong,
including 12,000 copies reporting Cedar at $56,000 when the real
best deal is Nova at $72,000 — a $16,000 miscalculation with no
warning anywhere. A 2,000-trial stress harness generalizes this beyond the one hand-picked example:
random small line sets, sorted correctly versus deliberately shuffled first, checked against an
independent brute-force maximum — the correctly-sorted version matched on all 2,000 trials, the
shuffled version failed on 1,794 of them. There's no defensive check worth adding inside
add() itself for this — verifying a whole deque's slopes are still decreasing on every
insert would cost the same O(n) the trick exists to avoid. The guarantee has to hold
at the call site, the same way a binary search's caller is responsible for a sorted array.
The fast query path has its own silent precondition. queryMonotonic
never resets its pointer backward — by design, that's where the O(1) amortized bound
comes from. Feed it a query x smaller than one already answered and it doesn't
recompute from the shallow end; it keeps whatever line the pointer is already sitting on, which is
provably correct for the old query but not necessarily for a smaller new one. There's no
crash and no obviously wrong-shaped output, just a value that's too low whenever the true winner
sits further toward the shallow end than the pointer already is. queryAny above exists
for exactly this case — same deque, a binary search instead of a stateful pointer, correct for
queries in any order at the cost of O(log n) instead of amortized O(1).
Time: building the deque is O(n) once the n lines are
already sorted by decreasing slope (O(n log n) if they still need sorting first) —
each line is pushed exactly once and popped at most once over the whole build, so the total number
of pop operations across every insert is bounded by n, not by n per
insert. Querying a non-decreasing sequence of m values costs O(n + m)
total, since the pointer advances at most n times across the entire run — amortized
O(1) per query, confirmed directly on this page's own five-query demo run: 3 total
pointer advances across 5 queries against a 4-line deque, never more than the deque's own size.
Queries in arbitrary order give up that amortized bound for queryAny's
O(log n) worst case per call, still exponentially cheaper than the naive
O(n) per-query scan this whole structure exists to avoid.
Space: O(n) for the deque — never more lines than were inserted, and
strictly fewer once any get popped as unnecessary.
This site's guide, Choosing a Convex Hull Algorithm, sets this entry aside up front, apart from the six pages it actually compares: there's no point set here at all, just many linear functions and a query for which one wins at a given x.