Convex hull trick

The convex hull trick is a technique (perhaps best classified as a data structure) used to determine efficiently, after preprocessing, which member of a set of linear functions in one variable attains an extremal value for a given value of the independent variable. It has little to do with convex hull algorithms.

History

The convex hull trick is perhaps best known in algorithm competitions from being required to obtain full marks in several USACO problems, such as MAR08 "acquire", which began to be featured in national olympiads after its debut in the IOI '02 task Batch Scheduling, which itself credits the technique to a 1995 paper (see references). Very few online sources mention it, and almost none describe it. It has been suggested (van den Hooff, 2010) that this is because the technique is "obvious" to anybody who has learned the sweep line algorithm for the line segment intersection problem.

The problem

Suppose that a large set of linear functions in the form $y = m_i x + b_i$ is given along with a large number of queries. Each query consists of a value of $x$ and asks for the minimum value of $y$ that can be obtained if we select one of the linear functions and evaluate it at $x$. For example, suppose our functions are $y=4$, $y=4/3+2/3\,x$, $y=12-3x$, and $y=3-1/2\,x$ and we receive the query $x=1$. We have to identify which of these functions assumes the lowest $y$-value for $x=1$, or what that value is. (It is the function $y=4/3+2/3\,x$, assuming a value of 2.)

The variation in which we seek the maximal line, not the minimal one, is a trivial modification and we will focus our attention on finding the minimal line.

Graphical representation of the lines in this example

When the lines are graphed, this is easy to see: we want to determine, at the $x$-coordinate 1 (shown by the red vertical line), which line is "lowest" ( has the lowest $y$-coordinate). Here it is the heavy dashed line, $y=4/3+2/3\,x$.

Naive algorithm

For each of the $Q$ queries, of course, we may simply evaluate every one of the linear functions, and determine which one has the least value for the given $x$-value. If $M$ lines are given along with $Q$ queries, the complexity of this solution is $\mathcal{O}(MQ)$. The "trick" enables us to speed up the time for this computation to $\mathcal{O}((Q+M)\lg M)$, a significant improvement.

Another example: APIO 2010 Commando

You are given:

• A sequence of $N$ positive integers ($1 \le N \le 10^6$).
• The integer coefficients of a quadratic function $f(x) = ax^2 + bx + c$, where $a < 0$.

The objective is to partition the sequence into contiguous subsequences such that the sum of $f$ taken over all subsequences is maximized, where the value of a subsequence is the sum of its elements.

An $O(N^2)$ dynamic programming approach is not hard to see. We define:

1. sum(i,j) = x[i] + x[i+1] + ... + x[j]
2. adjust(i,j) = a*sum(i,j)^2 + b*sum(i,j) + c

Then let

$\operatorname{dp}(n) = \max_{0 \le k < n} [\operatorname{dp}(k) + \operatorname{adjust}(k+1, n)]$.

Pseudocode:

dp[0] ← 0
for n ∈ [1..N]
    for k ∈ [0..n-1]
        dp[n] ← max(dp[n], dp[k] + adjust(k + 1 , n))

Now let's play around with the function "adjust".

Denote $\operatorname{sum}(1,x)$ by $\sigma(x)$. Then, for some value of $k$, we can write

$\begin{array}{rl} \operatorname{dp}(n) &= \operatorname{dp}(k) + a(\sigma(n)-\sigma(k))^2 + b(\sigma(n)-\sigma(k)) + c \\ &= \operatorname{dp}(k)+ a(\sigma(n)^2 - 2\sigma(n)\sigma(k) + \sigma(k)^2) + b(\sigma(n) - \sigma(k)) + c \\ &= (a\sigma(n)^2 + b\sigma(n) + c) + \operatorname{dp}(k) - 2a\sigma(n)\sigma(k) + a\sigma(k)^2 - b\sigma(k) \end{array}$

Now, let

1. $z = \sigma(n)$
2. $m = -2a\sigma(k)$
3. $p = \operatorname{dp}(k) + a\sigma(k)^2 - b\sigma(k)$

Then, we see that $mz + p$ is the quantity we aim to maximize by our choice of $k$. Adding $a\sigma(n)^2 + b\sigma(n) + c$ (which is independent of $k$) to the maximum gives the correct value of $\operatorname{dp}(n)$. Also, $z$ is independent of $k$, whereas $m$ and $p$ are independent of $n$, as required.

Unlike in task "acquire", we are interested in building the "upper envelope". We notice that the slope of the "maximal" line increases as $x$ increases. Since the problem statement indicates $a < 0$, the slope of each line is positive.

Suppose $k_2 > k_1$. For $k_1$ we have slope $m_1 = -2a \sigma(k_1)$. For $k_2$ we have slope $m_2 = -2a \sigma(k_2)$. But $\sigma(k_2) > \sigma(k_1)$, and since the given sequence is positive, so $m_2 > m_1$. We conclude that lines are added to our data structure in increasing order of slope.

Since $\sigma(n) > \sigma(n-1)$, query values are given in increasing order and a pointer walk suffices (it is not necessary to use binary search.)

Fully dynamic variant

The convex hull trick is easy to implement when all insertions are given before all queries (offline version) or when each new line inserted has a lower slope than any line currently in the envelope. Indeed, by using a deque, we can easily allow insertion of lines with higher slope than any other line as well. However, in some applications, we might have no guarantee of either condition holding. That is, each new line to be added may have any slope whatsoever, and the insertions may be interspersed with queries, so that sorting the lines by slope ahead of time is impossible, and scanning through an array to find the lines to be removed could take linear time per insertion

It turns out, however, that it is possible to support arbitrary insertions in amortized logarithmic time. To do this, we store the lines in an ordered dynamic set (such as C++'s std::set). Each line possesses the attributes of slope and y-intercept, the former being the key, as well as an extra $left$ field, the minimum $x$-coordinate at which this line is the lowest in the set. To insert a new line, we merely insert it into its correct position in the set, and then all the lines to be removed, if any, are contiguous with it. The procedure is then largely the same as for the case in which we always inserted lines of minimal slope: if the line to be added is $l_3$, the line to the left is $l_2$, and the line to the left of that is $l_1$, then we check if the $l_1$-$l_3$ intersection is to the left of the $l_1$-$l_2$ intersection; if so, $l_2$ is discarded and we repeat; similarly, if lines $l_4$ and $l_5$ are on the right, then $l_4$ can be removed if the $l_3$-$l_5$ intersection is to the left of the $l_3$-$l_4$ intersection, and this too is performed repeatedly until no more lines are to be discarded. We compute the new $left$ values (for $l_3$, it is the $l_2$-$l_3$ intersection, and for $l_4$, it is the $l_3$-$l_4$ intersection).

To handle queries, we keep another set, storing the same data but this time ordered by the $left$ value. When we insert or remove lines from that set (or update, in the case of $l_4$ above), we use the $left$ value from the element in that set to associate it with an element in this one. Whenever a query is made, therefore, all we have to do is to find the greatest $left$ value in this set that is less than the query value; the corresponding line is the optimal one .

References

• Brucker, P. (1995). Efficient algorithms for some path partitioning problems. Discrete Applied Mathematics, 62(1-3), 77-85.
• Christiano, Paul. (2007). Land acquisition. Retrieved from an archived copy of the competition problem set at http://tjsct.wikidot.com/usaco-mar08-gold
• Peng, Richard. (2008). USACO MAR08 problem 'acquire' analysis. Retrieved from http://ace.delos.com/TESTDATA/MAR08.acquire.htm
• van den Hooff, Jelle. (2010). Personal communication.
• Wang, Hanson. (2010). Personal communication.

Code

• C++ solution for "acquire"
• C++ solution for "commando"

External links

• APIO 2010