Dynamic Programming Optimisation with Convex Hull Trick :

Why Dynamic programming?

• Dynamic programming is a very useful method for solving a particular class of problems in which the problem is broken into smaller sub-problems and the optimal solution of sub-problems contribute towards the optimal solution of given problem.

• If you are new to Dynamic Programming you can read a good tutorial here: link1

• Most of the problems solved by DP(dynamic programming) seem to be of brute force type, but you can identify them by observing the repetative calculation of sub-problems and by formulating a recursive relationship to get the optimal soution.

What’s a Convex Hull Trick?

• Although it seems to be related to the Convex Hull Algorithm from its name, but it’s not. It is a “trick”, as its name suggests, in which from a set of linear function, the function which attains the extreme value for an independent variable is obtained effeciently by some preprocessing. Only because the soultion looks like an open convex polygon it is known as “Convex Hull Trick”.

• For simple understanding, consider N lines of the form:

  y=m_ix+c_i , ∀ i ∈[1,N]

• The problem is to find the line with extremum value of y for a particular value of x. Let’s consider finding the minimum value of y.

  

• From the figure you can see that the parts of lines marked as lower envelope gives us the required solution.

• Few simple observations that can be made are :

  • A part of line can be the solution for a continuous range of x.
  • As x increases, the slope of the required line keeps on decreasing and these parts of lines form an open convex hull.

• So, if you are given the set of lines initially, the you can sort the lines with decresasing value of slope and add then build the solution based on their point of intersection.

  

• To build the solution you should discard the lines that can’t be a part of the solution. As you can see the above image, the slopes of lines are such that :

  m_m > m_l > m_n

  First, consider you have only lines m & l. Then, add the line n to the set of line. Here, you can see that the x-co-ordinate of point C is less than the x-co-ordinate of point A. Hence, the line n attains minimum value even before the line l. From this you can see that the line l can be discarded from the solution set.

• After discarding all such unnecessary lines, you can maintain the lines with decresing slope and the x-co-ordinate of its point of intersection with its previous line. (Observe that these x-co-ordinates will be in increasing order).

• For the query, you can do binary search on the x-co-ordinate of point of intersections and and get the line with the minimum value of y effeciently in Ο(logN), where N is number of lines.

• PreProcessing time: Ο(NlogN).

• There is also a fully dynamic variant of this Convex Hull Trick in which the lines are added during the query time. For this a data structure like set can be used which maintain the sorted list of slopes of lines dynamically. The only difference is after each insertion of a new line(insertion of slope) into set, we check its intersection with its neighbouring elements in set and decide wheathter to discard it or not using the same condition as stated above. We should also check if any line already present in the set is discarded after the insertion of the line.

• You can also try solving this problem here, which is based on direct implementation of its dynamic variant.

How can you optimise DP with Convex Hull Trick?

• In some specific problems that can be solved by Dynamic Programming we can do faster calculation of the state using the Convex Hull Trick. In these type of problems, the recursive relation between the states is as follows:

  • dp_i = min(b_j*a_i + dp_j) ,where j ∈ [1,i-1]
  • b_i > b_j ,∀ i<j.

  Our task is to calculate dp_N from this relation. Here b_i and dp_i can be analogously interpreted as the slope and y-intercept for a line, and our problem of calculating the i’th state can be viewed as finding the minimum value of a line for x-co-ordinate a_i,which can be effeciently done using the convex hull trick. The slopes of the are given in the decreasing order here, so after calculating dp_i we can add a line with slope b_i and y-intercept dp_i directly to the right of the sorted list maintained for calculating further states.

• In the above problem if we directly calculate dp_i by taking i-1 steps for each i, the the time complexity turns out to be Ο(N²), but by using this optimisation technique we can calculate each state in Ο(logN) and the total complexity of the problem reduces to Ο(NlogN)

• This problem can also be more constrained by a condition:
  • a_i < a_j, ∀ i<j.

  In this case, as we know that the x-co-ordinates are in increasing order, we can just maintain a pointer to the line giving minimunm value and then update the pointer to the next line according to the query. Here the steps taken for binary search are replaced by some amortised constant steps to update the pointer to the next lines(decreasing slope order). So, the calculation of each state takes time Ο(1) and the total time complexity reduces to Ο(N)

• If there if no constraints given for a_i and b_i, then you can relate the problem with the dynamic variant of Convex Hull Trick. For this problem, we use the data structure set that maintains the lines in decreasing order of slopes along with dynamic insertions. Each insertion of line into set takes time Ο(logN) and calculation of each state takes time Ο(logN). So, the total time complexity will be Ο(NlogN). You should be cautious in using set when you are given a constraint for b_i because even though by both ways you get Ο(NlogN), set has a high proportionality time constant.

• You can try solving some problems here : link1 link2 link3
• Here’s an image just for fun :) img

………………………………………