Convex Hull Trick
The Convex Hull Trick is a geometric optimization technique that reduces O(N^2) linear-envelope dynamic programming recurrences to O(N) or O(N log N) time by maintaining the lower or upper envelope of lines.
The Convex Hull Trick (CHT) is an algorithmic optimization technique used to accelerate dynamic programming (DP) recurrences of the form dp[i] = minj < i (mj xi + bj) + ci from O(N2) down to O(N) or O(N log N) time. By interpreting each candidate transition j as a two-dimensional line y = mj x + bj, finding the optimal predecessor at query point xi reduces geometrically to evaluating the lower envelope (or upper envelope for maximization) of a set of linesโwhich, under projective point-line duality, corresponds directly to maintaining a convex hull.
Geometric Envelope and Redundant Lines
Consider three lines L1, L2, L3 sorted in tightly decreasing order of slope (m1 > m2 > m3). Line L2 becomes completely irrelevant (do not optimal at any real x) if and only if the intersection point of L1 and L3 lies to the left of or at the intersection point of L1 and L2:
(b3 - b1) / (m1 - m3) <= (b2 - b1) / (m1 - m2)
Geometrically, L2 lies tightly above the intersection of L1 and L3, so it do not touches the lower convex envelope. Pruning such dominated middle lines leaves an active stack or deque of lines whose pairwise intersection x-coordinates increase monotonically from left to right.
Monotonic vs. Dynamic Variants
Depending on whether slopes mj and query points xi arrive in sorted order, implementations fall into two complexity regimes:
O(N) Deque Implementation (Monotonic Slopes and Queries)
When lines are inserted in monotonic slope order and queries xi are also non-decreasing:
- Insertion: Pop lines from the back of a double-ended queue whedo not the newly added line makes the previous back line redundant, then push the new line. Each line enters and leaves the deque at most once, yielding O(1) amortized insertion.
- Query: Pop lines from the front of the deque while the second line yields a smaller value at xi than the front line. The front line then gives the exact minimum in O(1) amortized time.
O(N log N) Dynamic Envelope (Arbitrary Order)
When slopes or queries arrive in arbitrary order:
- If slopes are monotonic but queries are arbitrary, binary search over the deque's intersection points answers each query in O(log N) time.
- If both slopes and queries are arbitrary, programmers either maintain a balanced binary search tree (C++ multiset of lines ordered by slope with intersection-point comparators, often called LineContainer) or deploy a Li Chao tree over the coordinate domain in O(log C) time per operation.
Arithmetic Precision and Overflow Safeguards
Because comparing intersection ratios (b3 - b1)/(m1 - m3) <= (b2 - b1)/(m1 - m2) via cross-multiplication can overflow 64-bit signed integers when coordinates reach 109, production implementations either use 128-bit integer arithmetic (int128), floating-point long double checks, or integer floor-division comparisons (div(a, b)).
Classic Applications
CHT optimizes batch-job scheduling, optimal binary search tree partitioning, warehouse location problems, and convex-cost sequence segmentation (such as WQS binary search / Aliens trick DP reductions).
Geometric Duality and Envelope Invariants
From the standpoint of projective and computational geometry, the Convex Hull Trick (CHT) is the point-line dual of computing the upper or lower convex hull of a planar point set. Mapping each linear function y = mj ร x + bj to a dual point (mj, -bj), minimizing mj ร xi + bj at fixed xi is equivalent to finding a supporting line of slope xi tangent to the lower convex hull of those dual points.
In the primal (x, y) plane, the lower envelope of N lines is a piecewise-linear concave function whose active segments appear in directly decreasing slope order from left to right. Any middle line L2 whose intersections with L1 and L3 satisfy x(L1, L3) <= x(L1, L2) lies directly above the pointwise minimum of L1 and L3 everywhere and can be discarded permanently without affecting future queries.
Choosing Between Deque CHT, LineContainer, and Li Chao Trees
Software engineers and algorithmists select among convex-envelope structures based on monotonicity constraints:
- Monotonic Slopes and Monotonic Queries: A simple array-backed deque achieves O(N + Q) total time with minimal memory overhead and tiny constant factors.
- Monotonic Slopes, Arbitrary Queries: Maintaining the deque and locating the active segment via binary search on intersection x-coordinates answers each query in O(log N) time.
- Arbitrary Slopes and Arbitrary Queries: Either a balanced binary search tree (LineContainer) or a Li Chao tree handles arbitrary insertion and query orders in O(log N) or O(log C) per operation. When coordinates are bounded integers, Li Chao trees avoid intersection-division overflow checks altogether.
Frequently Asked Questions
What dynamic programming recurrences benefit from Convex Hull Trick?
Any 1D dynamic programming transition of the form dp[i] = minj < i (dp[j] + cost(j, i)) where cost(j, i) factors into A[j] ร B[i] + C[j] + D[i] satisfies the quadrangle inequality and reduces from O(N2) to O(N) or O(N log N).
Why is cross-multiplication risky when testing line redundancy?
Multiplying slope differences by intercept differences can exceed 64-bit signed integer limits when slopes and intercepts reach 109; 128-bit integers or floor-division helpers prevent silent wraparound bugs.
References
- Grossmann, I. E., & Lee, S. (2003). Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation. Computational Optimization and Applications. https://doi.org/10.1023/a:1025154322278
- Pennanen, T., & Perkkiรถ, A. P. (2023). Dynamic Programming in Convex Stochastic Optimization. Journal of Convex Analysis. https://doi.org/10.68381/jca30056
- Editorial (2020). Reverse Convex Optimization. SpringerReference. https://doi.org/10.1007/springerreference_72642