Solve equations of combing min and max functions

Question

How to solve an equations if it looks like as follows: $min\left\{d_1, max\{c_1,a_1*x+b_1\}\right\} + min\left\{d_2, max\{c_2,a_2*x+b_2\}\right\} + min\left\{d_3, max\{c_3,a_3*x+b_3\}\right\} = e$

Answer 1

Each term $\min\{d_i, \max\{c_i, a_i x + b_i\}\}$ has two "corner points" $\frac{c_i-b_i}{a_i}$ and $\frac{d_i - b_i}{a_i}$ where its behavior changes. A reasonable first step is to sort all the corner points from least to greatest, remembering the term they came from.

This takes $O(n \log n)$ time for a function with $n$ terms, but after doing so, searching for a place where the function equals $e$ can be done in $O(n)$ time. This is pretty good, considering that evaluating the function at a single point takes $O(n)$ time all on its own! And if you have to solve the equation for many different values of $e$, the sorting only has to be done once.

Start by evaluating the function at a value of $x$ smaller than the first corner point. Here, each term is equal to either $c_i$ or $d_i$, depending on the sign of the slope $a_i$.

From here, iterate through the corner points from least to greatest, keeping track of two things:

1. The current function value (which starts at the value you've chosen);
2. The current slope (which starts at $0$).

When you reach a corner point, you can update the function value (using the previous function value and the current slope) and the slope (which changes by $\pm a_i$ when we reach a corner of the $i^{\text{th}}$ term).

If the previous function value was smaller than $e$, and the new function value is bigger than $e$, or vice versa, then we can interpolate between the current corner point and the previous corner point to find the place where the function value is equal to $e$. (Between two corners, the function is linear, with a slope we know.)

If we're going to be solving equations for the same function multiple times, we might as well save the function values at each corner point, after we've computed them once. Once we've done that, a bisection search will solve the equation in only $O(\log n)$ time. (To help the bisection search along, we should remember the location of the minimum and maximum value we've computed.)