yohandi

A recent graduate with a strong interest in algorithms and data structures.

[Tutorial] DP Optimization: Convex Hull Trick

August 21, 2023 by Yohandi

algorithm dynamic-programming geometry optimization tutorial

"Geometry being useful", I copied that down from this blog. And yes, in any subject, geometry often steps in to offer a fresh perspective. The Convex Hull Trick is a testament to this, seamlessly blending algorithmic efficiency with geometric intuition. In this post, I will discuss pretty much about this method.

Motivational Problem

Suppose there are

KaTeX can only parse string typed expression

n

rectangles in a 2D Cartesian Plane, each defined by vertices

(0, 0)

and

(x_{i}, y_{i})

, along with a number

a_{i}

. We want to select some of these rectangles such that the area of their union minus the sum of the

a_{i}

values of the chosen rectangles is maximized.

Constraints given:

$1 \leq n \leq 1 0^{6}$
$1 \leq x_{i}, y_{i} \leq 1 0^{9}$ (for each $i$ such that $0 \leq i < n$ )
$0 \leq a_{i} \leq x_{i} \cdot y_{i}$ (for each $i$ such that $0 \leq i < n$ )
No nested rectangles exist

This problem comes straight from Codeforces Round 526 (Div. 1E).

Dynamic Programming Solution

Let's consider these

KaTeX can only parse string typed expression

(x_{i}, y_{i}, a_{i})

tuples:

[(6, 2, 4), (1, 6, 2), (2, 4, 3), (5, 3, 8)]]

Because no nested rectangles exist in all cases, we can sort these tuples by

KaTeX can only parse string typed expression

x

without losing their essences. Note that sorting by

x

in ascending order also sorts the tuples by

y

in descending order.

Denote

KaTeX can only parse string typed expression

dp_{i}

as the maximum value that can be achieved by selecting the

i

-th rectangle (from the sorted version) and some of the previous rectangles. Then, our answer will be

ans = 0 \leq i < n max dp_{i}

, where

dp_{i} = (x_{i} \cdot y_{i} - A_{i}) + max (0 \leq j < i max dp_{j} - x_{j} \cdot y_{i}, 0)

Parts explanation:

The $(x_{i} \cdot y_{i} - A_{i})$ part is obtained as the reward for selecting the $i$ -th rectangle.
The $dp_{j}$ part acts as an additional reward for selecting the $j$ -th rectangle.
The $- x_{j} \cdot y_{i}$ part, which is derived from $- min (x_{i}, x_{j}) \cdot min (y_{i}, y_{j})$ , is obtained as the consequence of selecting the $i$ -th rectangle with $j$ -th rectangle (and presumably any rectangle that maximizes the $dp_{j}$ value). Note that $x_{j} \cdot y_{i}$ is the intersection for the $i$ -th rectangle and the $j$ -rectangle. This part is important as the union area of the $i$ -th rectangle and the $j$ -th rectangle is $(x_{i} \cdot y_{i}) \cup (x_{j} \cdot y_{j}) = (x_{i} \cdot y_{i}) + (x_{j} \cdot y_{j}) - (x_{i} \cdot y_{i}) \cap (x_{j} \cdot y_{j})$ .

This dynamic programming solution works in

KaTeX can only parse string typed expression

O (n^{2})

; however, it is still not suffice as

n

might be

1 0^{6}

. We need an optimization towards it.

Convex Hull Trick

This is where our main optimization technique, the Convex Hull Trick, comes in handy. The Convex Hull Trick is a computational geometry used to manage a set of affine functions, constructing a lower / upper hull. To illustrate, suppose we are going to insert the following affine functions:

KaTeX can only parse string typed expression

- x + 4

- 2 x + 5

- 5 x + 8

, and

- 6 x + 10

, into our lower hull.

Notice that in our lower hull, we always want to have the intersection points of every two lines that are side by side sorted. Formally, if we have a set of affine functions in our lower hull, say

KaTeX can only parse string typed expression

f_{0} (x)

f_{1} (x)

\dots

, and

f_{n - 1} (x)

, with

p_{i}

representing the x-coordinate of the intersection point of

f_{i} (x)

and

f_{i + 1} (x)

, i.e.,

f_{i} (p_{i}) = f_{i + 1} (p_{i})

, for

0 \leq i < n - 2

; then, it is essential that

p_{0} > p_{1} > \dots > p_{n - 2}

(or sorted in the other way).

If there is a scenario where

KaTeX can only parse string typed expression

p_{i} = p_{i + 1}

, we can discard either

f_{i} (x)

f_{i + 1} (x)

. The choice depends on the gradient, considering whether it is lower / higher and negative / positive.

The implementation is as follows:

struct Line {
  long long m, c;
  Line(long long m, long long c) : m(m), c(c) {}

  long long y(long long x) { return m * x + c; }
  double intersect(Line other) const {
    return (double)(c - other.c) / (double)(other.m - m);
  }
};

vector<Line> ch;

void addLine(Line line) {
  auto comp = [&](const Line &a, const Line &b, const Line &c) -> bool {
    return a.intersect(b) > b.intersect(c); // p_0 > p_1 > ... > p_{n - 2}
  };

  while (ch.size() >= 2 && !comp(ch[ch.size() - 2], ch.back(), line)) {
    ch.pop_back();
  }

  ch.push_back(line);
}

The implementation above operates efficiently when the inserted gradient is in descending order. The reason will be explained later.

In our set of affine functions, it can be observed that:

$f_{0} (x)$ maximizes the value of $x$ for $x \in [p_{0}, \infty)$ ;
$f_{1} (x)$ maximizes the value of $x$ for $x \in [p_{1}, p_{0}]$ ;
$\dots$
$f_{n - 2} (x)$ maximizes the value of $x$ for $x \in [p_{n - 2}, p_{n - 3}]$ ;
$f_{n - 1} (x)$ maximizes the value of $x$ for $x \in (- \infty, p_{n - 2}]$ .

Using this observation, whenever we want to look up for

KaTeX can only parse string typed expression

i

that maximizes

f_{i} (x)

for an

x

, we can perform a binary search on the intersection points to determine the domain where

x

lies.

int optimalLine(long long x) {
  auto p = [&](const int i) -> double { return ch[i].intersect(ch[i + 1]); };

  return lower_bound(ch.begin(), ch.end() - 1, x,
                     [&](const Line &line, long long val) {
                       int idx = &line - &ch[0];
                       return p(idx) > val;
                     }) -
         ch.begin();
}

Reverting to our primary dynamic programming solution, where we had:

dp_{i} = (x_{i} \cdot y_{i} - A_{i}) + max (0 \leq j < i max dp_{j} - x_{j} \cdot y_{i}, 0)

Regardless of the value of

KaTeX can only parse string typed expression

j

, we consistently add

x_{i} \cdot y_{i} - A_{i}

dp_{i}

; thus, this can be omitted from our optimization process. An affine function

f_{i} (x) = m_{i} \cdot x + c_{i}

is formed by assigning

m_{i}

- x_{i}

and

c_{i}

dp_{i}

. If

C

represents a constant in

dp_{i}

, then

C = x_{i} \cdot y_{i} - A_{i}

. Our

dp

equation can then be expressed as:

dp_{i} = max (0 \leq j < i max (m_{j} \cdot y_{i} + c_{j}), 0) + C

To further simplify our dynamic programming, we may also add a line

KaTeX can only parse string typed expression

f_{- 1} (x) = 0

to handle the

max (\dots, 0)

component.

dp_{i} = - 1 \leq j < i max (m_{j} \cdot y_{i} + c_{j}) + C

The solution's flow is as follows:

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  struct InputFormat {
    long long x, y, A;
    bool operator<(const InputFormat &other) const {
      return tie(x, y, A) < tie(other.x, other.y, other.A);
    }
  };

  long long N, ans = 0;
  cin >> N;

  vector<InputFormat> arr(N);
  vector<long long> x(N), y(N), A(N), dp(N);

  for (auto &a : arr)
    cin >> a.x >> a.y >> a.A;
  sort(arr.begin(), arr.end());

  for (int i = 0; i < N; ++i)
    tie(x[i], y[i], A[i]) = make_tuple(arr[i].x, arr[i].y, arr[i].A);

  addLine(Line(0, 0));
  for (int i = 0; i < N; ++i) {
    dp[i] = ch[optimalLine(y[i])].y(y[i]) + (x[i] * y[i] - A[i]);
    addLine(Line(-x[i], dp[i]));

    ans = max(ans, dp[i]);
  }

  cout << ans << endl;
  return 0;
}

The gradient of the inserted line is guaranteed to be in descending order as the gradient is

KaTeX can only parse string typed expression

- x_{i}

and

x_{i}

is in ascending order. This explains the previous

addLine

implementation. Querying the

optimalLine

only performs binary search from

0

n - 1

, resulting in a complexity of

O (lo g n)

per query. The armortized total operations in

addLine

function is

O (n)

. The overall solution operates in

O (n lo g n)

. My full solution is accessible here.

Variation

Upper Hull

In a case where we have a minimization problem, we want to look up for the upper hull. Some comparisons in the code, especially in

KaTeX can only parse string typed expression

comp

within

addLine

and the binary search in

optimalLine

, need to be inverted.

Dynamic Convex Hull Trick

In this particular case, we do not have the guarantee of having the gradient insertion sorted, whether it is in ascending order or in descending order; consequently, we no longer can use

KaTeX can only parse string typed expression

std::vector

for our data structure. We may use

std::set

to maintain the dynamic gradients. Or... we may use Li Chao Tree, which I will discuss in the upcoming post.

And there we have it! I have always found the Convex Hull Trick fascinating, especially when it comes to refine a naive

KaTeX can only parse string typed expression

O (n^{2})

dynamic programming approach down to

O (n lo g n)

. Of course, it still requires an additional property, which is to have the dynamic programming rewritable as an affine function. Some other DP optimizations, such as Divide and Conquer, Knuth, and more will probably discussed in the future posts as well! Stay tuned!

← [Tutorial] Variations of Golden-section Search on a Density Function [Tutorial] Li Chao Tree →