| Latest revision |
Your text |
| Line 14: |
Line 14: |
| | ==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 M)</math>, a significant improvement. | | 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 M)</math>, a significant improvement. |
| − |
| |
| − | ==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: 2/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>
| |
| − | ===Etymology===
| |
| − | The term ''convex hull'' is sometimes misused to mean ''upper/lower envelope''. If we consider the "optimal" segment of each of the three lines (ignoring <math>y=4</math>), what we see is the ''lower envelope'' of the lines: nothing more or less than the set of points obtained by choosing the lowest point for every possible <math>x</math>-coordinate. (The lower envelope is highlighted in green in the diagram above.) Notice that the set bounded above by the lower envelope is convex. We could imagine the lower envelope being the upper convex hull of some set of points, and thus the name ''convex hull trick'' arises. (Notice that the problem we are trying to solve can again be reformulated as finding the intersection of a given vertical line with the lower envelope.)
| |
| − | ===Adding a line===
| |
| − | <p>As we have seen, if the set of relevant lines has already been determined and sorted, it becomes trivial to answer any query in <math>\mathcal{O}(\lg N)</math> time ''via'' binary search. Thus, if we can add lines one at a time to our data structure, recalculating this information quickly with each addition, we have a workable algorithm: start with no lines at all (or one, or two, depending on implementation details) and add lines one by one until all lines have been added and our data structure is complete.</p>
| |
| − | <p>Suppose that we are able to process all of the lines before needing to answer any of the queries. Then, we can sort them in descending order by slope beforehand, and merely add them one by one. When adding a new line, some lines may have to be removed because they are no longer relevant. If we imagine the lines to lie on a [[stack]], in which the most recently added line is at the top, as we add each new line, we consider if the line on the top of the stack is relevant anymore; if it still is, we push our new line and proceed. If it is not, we pop it off and repeat this procedure until either the top line is not worthy of being discarded or there is only one line left (the one on the bottom, which can never be removed).</p>
| |
| − | <p>How, then, can we determine if the line should be popped from the stack? Suppose <math>l_1</math>, <math>l_2</math>, and <math>l_3</math> are the second line from the top, the line at the top, and the line to be added, respectively. Then, <math>l_2</math> becomes irrelevant if and only if the intersection point of <math>l_1</math> and <math>l_3</math> is to the left of the intersection of <math>l_1</math> and <math>l_2</math>. (This makes sense because it means that the interval in which <math>l_3</math> is minimal subsumes that in which <math>l_2</math> was previously.) We have assumed for the sake of simplicity that no three lines are concurrent.</p>
| |
| − | ===Analysis===
| |
| − | <p>Clearly, the space required is <math>\mathcal{O}(M)</math>: we need only store the sorted list of lines, each of which is defined by two real numbers.</p>
| |
| − | <p>The time required to sort all of the lines by slope is <math>\mathcal{O}(M \lg M)</math>. When iterating through them, adding them to the envelope one by one, we notice that every line is pushed onto our "stack" exactly once and that each line can be popped at most once. For this reason, the time required overall is <math>\mathcal{O}(M)</math> for this step; although each individual line, when being added, can theoretically take up to linear time if almost all of the already-added lines must now be removed, the total time is limited by the total number of times a line can be removed. The cost of sorting dominates, and the construction time is <math>\mathcal{O}(M \lg M).</math></p>
| |
| − |
| |
| − | ==Case study: USACO MAR08 acquire==
| |
| − | ===Problem===
| |
| − | <p>Up to 50000 rectangles of possibly differing dimensions are given and it is desired to acquire all of them. To acquire a subset of these rectangles incurs a cost that is proportional to neither the size of the subset nor to its total area but rather the product of the width of the widest rectangle in the subset times the height of the tallest rectangle in the subset. We wish to cleverly partition the rectangles into groups so that the total cost is minimized; what is the total cost if we do so? Rectangles may not be rotated; that is, we may not interchange the length and width of a rectangle.</p>
| |
| − |
| |
| − | ===Observation 1: Irrelevant rectangles===
| |
| − | Suppose that both of rectangle A's dimensions equal or exceed the corresponding dimensions of rectangle B. Then, we may remove rectangle B from the input because its presence cannot affect the answer, because we can merely compute an optimal solution without it and then insert it into whichever subset contains rectangle A without changing the cost. Rectangle B, then, is irrelevant. We first sort the rectangles in ascending order of height and then sweep through them in linear time to remove irrelevant rectangles. What remains is a list of rectangles in which height is monotonically increasing and width is monotonically decreasing. (Otherwise, a contradiction would exist to our assumption that all irrelevant rectangles have been removed.)
| |
| − |
| |
| − | ===Observation 2: Contiguity===
| |
| − | In the sorted list of remaining rectangles, ''each subset to be acquired is contiguous''. Thus, for example, if there are four rectangles, numbered 1, 2, 3, 4 according to their order in the sorted list, it is possible for the optimal partition to be <math>\{\{1,2\},\{3,4\}\}</math> but not <math>\{\{1,4\},\{2,3\}\}</math>; in the latter, <math>\{2,3\}</math> is contiguous but <math>\{1,4\}</math> is not. This is true because, in any subset, if rectangle A is the tallest and rectangle B is the widest, then all rectangles between them in the sorted list may be added to this subset without any additional cost, and therefore we will always assume that this occurs, making each subset contiguous.
| |
| − |
| |
| − | ===DP solution===
| |
| − | The remaining problem then is how to divide up the list of rectangles into contiguous subsets while minimizing the total cost. This problem admits a <math>\Theta(N^2)</math> solution by [[dynamic programming]], the pseudocode for which is shown below: ''Note that it is assumed that the list of rectangles comes "cooked"; that is, irrelevant rectangles have been removed and the remaining rectangles sorted.''
| |
| − | <pre>
| |
| − | input N
| |
| − | for i ∈ [1..N]
| |
| − | input rect[i].h
| |
| − | input rect[i].w
| |
| − | let cost[0] = 0
| |
| − | for i ∈ [1..N]
| |
| − | let cost[i] = ∞
| |
| − | for j ∈ [0..i-1]
| |
| − | cost[i] = min(cost[i],cost[j]+rect[i].h*rect[j+1].w)
| |
| − | print cost[N]
| |
| − | </pre>
| |
| − | In the above solution, <code>cost[k]</code> stores the minimum possible total cost for acquiring the first <code>k</code> rectangles. Obviously, <code>cost[0]=0</code>. To compute <code>cost[i]</code> when <code>i</code> is not zero, we notice that it is equal to the total cost of acquiring all previous subsets plus the total cost of acquiring the subset containing rectangle number <code>i</code>; the latter may be readily calculated if the size of the latter subset is known, because it is merely the width of the first times the height of the last (rectangle number <code>i</code>). We wish to minimize this, hence <code>cost[i] = min(cost[i],cost[j]+rect[i].h*rect[j+1].w).</code> (Notice that <code>j</code> is the last rectangle of the previous subset, looping over all possible choices.)
| |
| − | Unfortunately, <math>\Theta(N^2)</math> is too slow when <math>N=50000</math>, so a better solution is needed.
| |
| − |
| |
| − | ===Observation 3: Convexity===
| |
| − | 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>
| |
| − | input N
| |
| − | for i ∈ [1..N]
| |
| − | input rect[i].h
| |
| − | input rect[i].w
| |
| − | let E = empty lower envelope structure
| |
| − | let cost[0] = 0
| |
| − | add the line y=mx+b to E, where m=rect[1].w and b=cost[0] //b is zero
| |
| − | for i ∈ [1..N]
| |
| − | cost[i] = E.query(rect[i].h)
| |
| − | if i<N
| |
| − | E.add(m=rect[i+1].w,b=cost[i])
| |
| − | print cost[N]
| |
| − | </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 (that is, no query occurs further left than its predecessor, so that no line chosen has a greater slope than the previous one chosen), 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.
| |
| | | | |
| | ==Another example: APIO 2010 Commando== | | ==Another example: APIO 2010 Commando== |
