13.17 Convex Hull Trick

Many dynamic programming solutions are correct but too slow.

algorithmsdynamic-programming

13.17 Convex Hull Trick

Many dynamic programming solutions are correct but too slow. The recurrence is easy to write, the state is well defined, and the base cases are clean, yet each state scans too many previous states. Convex hull trick is one of the standard techniques for reducing such transition costs.

The technique applies when a recurrence can be rewritten as a minimum or maximum over a set of linear functions. Instead of checking every previous state, we maintain a collection of lines and query the best line at a given point.

This optimization appears in scheduling, partitioning, sequence optimization, transportation planning, and cost minimization problems. It is not a general-purpose DP accelerator. It works only when the recurrence has the right algebraic shape.

Problem

Given a dynamic programming recurrence that scans many previous states, how can we reduce transition time when each candidate can be expressed as a line?

The Slow Pattern

A common recurrence has the form:

$$ dp[i] = \min_{j<i} ( dp[j] + cost(j,i) ) $$

A direct implementation is:

for i := 1; i <= n; i++ {

    dp[i] = inf

    for j := 0; j < i; j++ {

        dp[i] = min(
            dp[i],
            dp[j]+cost(j, i),
        )
    }
}

If there are (n) states and each state scans (O(n)) previous states, the total cost is:

$$ O(n^2) $$

Convex hull trick is useful when the expression inside the minimum can be transformed into:

$$ m_j x_i + b_j $$

where:

  • (m_j) is a slope depending on (j)
  • (b_j) is an intercept depending on (j)
  • (x_i) is the query point depending on (i)

Each previous state becomes a line.

Each current state asks for the lowest line at (x_i).

Rewriting a Recurrence

Suppose the recurrence is:

$$ dp[i] = x_i^2 + \min_{j<i} ( dp[j] + a_j^2 - 2a_jx_i ) $$

The term:

$$ x_i^2 $$

does not depend on (j), so it can be added after the minimum.

The candidate part is:

$$ (-2a_j)x_i + (dp[j]+a_j^2) $$

This is a line:

$$ y = mx + b $$

where:

$$ m=-2a_j $$

and:

$$ b=dp[j]+a_j^2 $$

Now each previous state (j) contributes one line. To compute (dp[i]), query the minimum line at (x_i), then add (x_i^2).

The Data Structure View

Convex hull trick maintains a set of lines and supports two operations:

add line y = mx + b

query minimum y-value at x

Depending on assumptions, these operations can be implemented in different ways.

Assumption Typical Structure
Slopes added in sorted order, queries monotonic Deque hull
Arbitrary insertion and query Li Chao tree
Offline queries Sorted hull plus binary search

The deque version is the simplest and fastest, but it requires monotonicity.

Why Lines Can Be Removed

Suppose we are minimizing.

If one line is never lower than another line for any future query, it is useless and can be discarded.

For example:

line A is always above line B

Then line A will never produce an optimal value.

The hull stores only lines that may be optimal for some interval of (x)-values.

This is why the technique is called a hull: it keeps the lower envelope of a set of lines.

Line Intersection Intuition

Two lines:

$$ y=m_1x+b_1 $$

and:

$$ y=m_2x+b_2 $$

intersect at:

$$ x= \frac{b_2-b_1}{m_1-m_2} $$

For minimization, one line is better on one side of the intersection and the other line is better on the other side.

The hull keeps lines in the order in which they become optimal.

A Deque-Based Hull

When slopes are added in monotonic order and query points are also monotonic, a deque works well.

Each line is stored in order.

When a new line is added, remove lines from the back that become irrelevant.

When querying, remove lines from the front while the next line is better at the current (x).

Implementation

The following implementation uses integer arithmetic and compares line values directly. It avoids floating-point intersection calculations.

type Line struct {
    M int64
    B int64
}

func (l Line) Value(x int64) int64 {
    return l.M*x + l.B
}

type Hull struct {
    lines []Line
}

func bad(a, b, c Line) bool {
    return (b.B-a.B)*(a.M-c.M) >=
        (c.B-a.B)*(a.M-b.M)
}

func (h *Hull) Add(line Line) {

    for len(h.lines) >= 2 {
        n := len(h.lines)

        if !bad(h.lines[n-2], h.lines[n-1], line) {
            break
        }

        h.lines = h.lines[:n-1]
    }

    h.lines = append(h.lines, line)
}

func (h *Hull) Query(x int64) int64 {

    for len(h.lines) >= 2 &&
        h.lines[1].Value(x) <= h.lines[0].Value(x) {

        h.lines = h.lines[1:]
    }

    return h.lines[0].Value(x)
}

This version assumes:

slopes are added in sorted order

queries x are nondecreasing

we are minimizing

If those assumptions are false, this implementation is not valid.

Applying the Hull to DP

For the recurrence:

$$ dp[i] = x_i^2 + \min_{j<i} ( dp[j]+a_j^2-2a_jx_i ) $$

we add a line for each completed state:

$$ m=-2a_j $$

$$ b=dp[j]+a_j^2 $$

Then query at:

$$ x=x_i $$

Implementation skeleton:

dp[0] = base

hull.Add(Line{
    M: -2 * a[0],
    B: dp[0] + a[0]*a[0],
})

for i := 1; i < n; i++ {

    best := hull.Query(x[i])

    dp[i] = x[i]*x[i] + best

    hull.Add(Line{
        M: -2 * a[i],
        B: dp[i] + a[i]*a[i],
    })
}

The original transition scanned all previous states.

The optimized version queries a data structure.

Complexity

With the monotonic deque version:

$$ O(1) $$

amortized time per insertion and query.

Total time:

$$ O(n) $$

This is a major improvement over:

$$ O(n^2) $$

Memory:

$$ O(n) $$

for the stored lines.

If a Li Chao tree is required, operations are usually:

$$ O(\log X) $$

where (X) is the coordinate range.

Recognizing Convex Hull Trick

Look for recurrences of the form:

$$ dp[i] = \min_{j<i} ( A(j)B(i) + C(j) + D(i) ) $$

or:

$$ dp[i] = \max_{j<i} ( A(j)B(i) + C(j) + D(i) ) $$

The key is separability:

  • terms depending only on (i)
  • terms depending only on (j)
  • one product term combining (i) and (j)

If it can be rewritten as:

$$ m_jx_i+b_j $$

convex hull trick may apply.

Common Mistakes

Applying It Without Linear Form

If candidates cannot be expressed as lines, convex hull trick does not apply.

The recurrence must reduce to:

slope times query plus intercept

Ignoring Monotonicity Assumptions

The deque implementation requires ordered slopes and monotonic queries.

Without these properties, use another structure.

Integer Overflow

Line evaluation computes:

m*x + b

Values may exceed 32-bit or even 64-bit ranges.

Use appropriate numeric types.

Wrong Min/Max Direction

A lower hull solves minimization.

An upper hull solves maximization.

The comparison signs differ.

Floating-Point Intersections

Avoid floats when integer comparisons are enough.

Precision errors can corrupt hull construction.

Debugging Strategy

When implementing convex hull trick, first write the slow DP.

Then write the optimized version.

Run both on small random inputs and compare outputs.

This catches almost every implementation error.

for test := 0; test < 10000; test++ {
    gotSlow := SolveSlow(input)
    gotFast := SolveFast(input)

    if gotSlow != gotFast {
        panic("mismatch")
    }
}

Convex hull trick is algebraically elegant but easy to miscode. A brute-force verifier is the safest development tool.

Takeaway

Convex hull trick optimizes dynamic programming recurrences whose transitions can be represented as queries over linear functions. Each previous state contributes a line, each current state queries the best line at a point, and the hull discards lines that can never be optimal. Under monotonic slope and query assumptions, the deque implementation reduces many (O(n^2)) recurrences to (O(n)). The technique is powerful, but narrow: before using it, verify the recurrence has a true linear form and that the data structure assumptions match the input.