Convex hull trick - Revision history

Jargon: Reverted edits by 172.70.114.237 (talk) to last revision by TYeung

2023-09-13T02:24:24Z

Reverted edits by 172.70.114.237 (talk) to last revision by TYeung

172.70.114.237: /* The technique */

2023-08-29T16:05:55Z

‎The technique

172.70.114.237: /* Case study: USACO MAR08 acquire */

2023-08-29T16:05:24Z

‎Case study: USACO MAR08 acquire

TYeung: Undo revision 2205 by 162.158.63.50 (talk)

2023-07-19T15:08:28Z

Undo revision 2205 by 162.158.63.50 (talk)

162.158.63.50: /* Adding a line */ The intersection has to below, not left

2020-12-25T09:20:04Z

‎Adding a line: The intersection has to below, not left

108.162.210.222: /* Observation 3: Convexity */

2018-09-30T21:42:35Z

‎Observation 3: Convexity

115.249.18.25: /* Observation 1: Irrelevant rectangles */

2016-09-15T14:49:57Z

‎Observation 1: Irrelevant rectangles

115.249.18.25: /* Observation 1: Irrelevant rectangles */

2016-09-15T14:34:56Z

‎Observation 1: Irrelevant rectangles

27.67.36.3: /* The problem */

2016-08-03T10:09:44Z

‎The problem

189.53.119.166: /* History */

2015-11-11T05:14:43Z

‎History

@@ Line 14: / Line 14: @@
 ==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.
 ==Another example: APIO 2010 Commando==

@@ Line 14: / Line 14: @@
 ==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.
 ==Another example: APIO 2010 Commando==

@@ Line 27: / Line 27: @@
 <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>
 ==Another example: APIO 2010 Commando==

@@ Line 23: / Line 23: @@
 <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 below 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>
+<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>

@@ Line 23: / Line 23: @@
 <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>
+<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 below 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>

@@ 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:
 <pre>
-input N
+input  N
 for i ∈ [1..N]
       input rect[i].h

@@ Line 33: / Line 33: @@
 ===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. How is this assumption made?(Otherwise, a contradiction would exist to our assumption that all irrelevant rectangles have been removed.)
+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===

@@ Line 10: / Line 10: @@
 <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==

@@ Line 2: / Line 2: @@
 ==History==
-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 {{problem|ioi0221|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 convex hull trick is perhaps best known in algorithm competitions 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 {{problem|ioi0221|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==