Editing Convex hull trick
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 2: | Line 2: | ||
==History== | ==History== | ||
− | The convex hull trick is perhaps best known in algorithm | + | The convex hull trick is perhaps best known in algorithm competition from being required to obtain full marks in several USACO problems, such as [http://tjsct.wikidot.com/usaco-mar08-gold MAR08 "acquire"], which began to be featured in national olympiads after its debut in the IOI '02 task [http://ioinformatics.org/locations/ioi02/contest/day2/batch/batch.pdf Batch Scheduling], which itself credits the technique to a 1995 paper (see references). Very few online sources mention it, and almost none describe it. (The technique might not be considered important enough, or people might want to avoid providing the information to other countries' IOI teams.) |
==The problem== | ==The problem== | ||
Line 10: | Line 10: | ||
<p>[[File:Convex_hull_trick1.png|200px|thumb|right|Graphical representation of the lines in this example]] | <p>[[File:Convex_hull_trick1.png|200px|thumb|right|Graphical representation of the lines in this example]] | ||
− | When the lines are graphed, this is easy to see: we want to determine, at the <math>x</math>-coordinate 1 (shown by the red vertical line), which line is "lowest" ( has the lowest <math>y</math>-coordinate). Here it is the heavy dashed line, <math>y=4/3+2/3\,x</math>.</p> | + | When the lines are graphed, this is easy to see: we want to determine, at the <math>x</math>-coordinate 1 (shown by the red vertical line), which line is "lowest" (has the lowest <math>y</math>-coordinate). Here it is the heavy dashed line, <math>y=4/3+2/3\,x</math>.</p> |
==Naive algorithm== | ==Naive algorithm== | ||
− | For each of the <math>Q</math> queries, of course, we may simply evaluate every one of the linear functions, and determine which one has the least value for the given <math>x</math>-value. If <math>M</math> lines are given along with <math>Q</math> queries, the complexity of this solution is <math>\mathcal{O}(MQ)</math>. The "trick" enables us to speed up the time for this computation to <math>\mathcal{O}((Q+M)\lg | + | For each of the <math>Q</math> queries, of course, we may simply evaluate every one of the linear functions, and determine which one has the least value for the given <math>x</math>-value. If <math>M</math> lines are given along with <math>Q</math> queries, the complexity of this solution is <math>\mathcal{O}(MQ)</math>. The "trick" enables us to speed up the time for this computation to <math>\mathcal{O}((Q+M)\lg Q)</math>, a significant improvement. |
==The technique== | ==The technique== | ||
− | <p>Consider the diagram above. Notice that the line <math>y=4</math> will ''never'' be the lowest one, regardless of the <math>x</math>-value. Of the remaining three lines, ''each one is the minimum in a single contiguous interval'' (possibly having plus or minus infinity as one bound). That is, the heavy dotted line is the best line at all <math>x</math>-values left of its intersection with the heavy solid line; the heavy solid line is the best line between that intersection and its intersection with the light solid line; and the light solid line is the best line at all <math>x</math>-values greater than that. Notice also that, as <math>x</math> increases, the slope of the minimal line decreases: | + | <p>Consider the diagram above. Notice that the line <math>y=4</math> will ''never'' be the lowest one, regardless of the <math>x</math>-value. Of the remaining three lines, ''each one is the minimum in a single contiguous interval'' (possibly having plus or minus infinity as one bound). That is, the heavy dotted line is the best line at all <math>x</math>-values left of its intersection with the heavy solid line; the heavy solid line is the best line between that intersection and its intersection with the light solid line; and the light solid line is the best line at all <math>x</math>-values greater than that. Notice also that, as <math>x</math> increases, the slope of the minimal line decreases: 4/3, -1/2, -3. Indeed, it is not difficult to see that this is ''always'' true.</p> |
<p>Thus, if we remove "irrelevant" lines such as <math>y=4</math> in this example (the lines which will never give the minimum <math>y</math>-coordinate, regardless of the query value) and sort the remaining lines by slope, we obtain a collection of <math>N</math> intervals (where <math>N</math> is the number of lines remaining), in each of which one of the lines is the minimal one. If we can determine the endpoints of these intervals, it becomes a simple matter to use [[binary search]] to answer each query.</p> | <p>Thus, if we remove "irrelevant" lines such as <math>y=4</math> in this example (the lines which will never give the minimum <math>y</math>-coordinate, regardless of the query value) and sort the remaining lines by slope, we obtain a collection of <math>N</math> intervals (where <math>N</math> is the number of lines remaining), in each of which one of the lines is the minimal one. If we can determine the endpoints of these intervals, it becomes a simple matter to use [[binary search]] to answer each query.</p> | ||
===Etymology=== | ===Etymology=== | ||
Line 43: | Line 43: | ||
input N | input N | ||
for i ∈ [1..N] | for i ∈ [1..N] | ||
− | input rect[ | + | input rect[N].h |
− | input rect[ | + | input rect[N].w |
let cost[0] = 0 | let cost[0] = 0 | ||
for i ∈ [1..N] | for i ∈ [1..N] | ||
Line 58: | Line 58: | ||
Let <math>m_j=\mathrm{rect}[j+1].w</math>, <math>b_j=\mathrm{cost}[j]</math>, and <math>x=\mathrm{rect}[i].h</math>. Then, it is clear that the inner loop in the above DP solution is actually trying to minimize the function <math>y=m_j x + b_j</math> by choosing <math>j</math> appropriately. That is, it is trying to solve exactly the problem discussed in this article. Thus, assuming we have implemented the lower envelope data structure discussed in this article, the improved code looks as follows: | Let <math>m_j=\mathrm{rect}[j+1].w</math>, <math>b_j=\mathrm{cost}[j]</math>, and <math>x=\mathrm{rect}[i].h</math>. Then, it is clear that the inner loop in the above DP solution is actually trying to minimize the function <math>y=m_j x + b_j</math> by choosing <math>j</math> appropriately. That is, it is trying to solve exactly the problem discussed in this article. Thus, assuming we have implemented the lower envelope data structure discussed in this article, the improved code looks as follows: | ||
<pre> | <pre> | ||
− | input | + | input N |
for i ∈ [1..N] | for i ∈ [1..N] | ||
− | input rect[ | + | input rect[N].h |
− | input rect[ | + | input rect[N].w |
let E = empty lower envelope structure | let E = empty lower envelope structure | ||
let cost[0] = 0 | let cost[0] = 0 | ||
Line 71: | Line 71: | ||
print cost[N] | print cost[N] | ||
</pre> | </pre> | ||
− | Notice that the lines are already being given in descending order of slope, so that each line is added "at the right"; this is because we already sorted them by width. The query step can be performed in logarithmic time, as discussed, and the addition step in amortized constant time, giving a <math>\Theta(N\lg N)</math> solution. We can modify our data structure slightly to take advantage of the fact that query values are non-decreasing | + | Notice that the lines are already being given in descending order of slope, so that each line is added "at the right"; this is because we already sorted them by width. The query step can be performed in logarithmic time, as discussed, and the addition step in amortized constant time, giving a <math>\Theta(N\lg N)</math> solution. We can modify our data structure slightly to take advantage of the fact that query values are non-decreasing, and replace the binary search with a [[pointer walk]], reducing query time to amortized constant as well and giving a <math>\Theta(N)</math> solution for the DP step. The overall complexity, however, is still <math>O(N\lg N)</math>, due to the sorting step. |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
==Fully dynamic variant== | ==Fully dynamic variant== | ||
− | <p>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 | + | <p>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.</p> |
<p>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 <code>std::set</code>). Each line possesses the attributes of slope and y-intercept, the former being the key, as well as an extra <math>left</math> field, the minimum <math>x</math>-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 <math>l_3</math>, the line to the left is <math>l_2</math>, and the line to the left of that is <math>l_1</math>, then we check if the <math>l_1</math>-<math>l_3</math> intersection is to the left of the <math>l_1</math>-<math>l_2</math> intersection; if so, <math>l_2</math> is discarded and we repeat; similarly, if lines <math>l_4</math> and <math>l_5</math> are on the right, then <math>l_4</math> can be removed if the <math>l_3</math>-<math>l_5</math> intersection is to the left of the <math>l_3</math>-<math>l_4</math> intersection, and this too is performed repeatedly until no more lines are to be discarded. We compute the new <math>left</math> values (for <math>l_3</math>, it is the <math>l_2</math>-<math>l_3</math> intersection, and for <math>l_4</math>, it is the <math>l_3</math>-<math>l_4</math> intersection).</p> | <p>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 <code>std::set</code>). Each line possesses the attributes of slope and y-intercept, the former being the key, as well as an extra <math>left</math> field, the minimum <math>x</math>-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 <math>l_3</math>, the line to the left is <math>l_2</math>, and the line to the left of that is <math>l_1</math>, then we check if the <math>l_1</math>-<math>l_3</math> intersection is to the left of the <math>l_1</math>-<math>l_2</math> intersection; if so, <math>l_2</math> is discarded and we repeat; similarly, if lines <math>l_4</math> and <math>l_5</math> are on the right, then <math>l_4</math> can be removed if the <math>l_3</math>-<math>l_5</math> intersection is to the left of the <math>l_3</math>-<math>l_4</math> intersection, and this too is performed repeatedly until no more lines are to be discarded. We compute the new <math>left</math> values (for <math>l_3</math>, it is the <math>l_2</math>-<math>l_3</math> intersection, and for <math>l_4</math>, it is the <math>l_3</math>-<math>l_4</math> intersection).</p> | ||
− | <p>To handle queries, we keep ''another'' set, storing the same data but this time ordered by the <math>left</math> value. When we insert or remove lines from that set | + | <p>To handle queries, we keep ''another'' set, storing the same data but this time ordered by the <math>left</math> value. When we insert or remove lines from that set, we use the <math>left</math> 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 <math>left</math> value in this set that is less than the query value; the corresponding line is the optimal one.</p> |
==References== | ==References== | ||
Line 126: | Line 84: | ||
* Christiano, Paul. (2007). Land acquisition. Retrieved from an archived copy of the competition problem set at [http://tjsct.wikidot.com/usaco-mar08-gold http://tjsct.wikidot.com/usaco-mar08-gold] | * Christiano, Paul. (2007). Land acquisition. Retrieved from an archived copy of the competition problem set at [http://tjsct.wikidot.com/usaco-mar08-gold 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 http://ace.delos.com/TESTDATA/MAR08.acquire.htm] | * Peng, Richard. (2008). USACO MAR08 problem 'acquire' analysis. Retrieved from [http://ace.delos.com/TESTDATA/MAR08.acquire.htm http://ace.delos.com/TESTDATA/MAR08.acquire.htm] | ||
− | |||
* Wang, Hanson. (2010). Personal communication. | * Wang, Hanson. (2010). Personal communication. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |