Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function is a convex piecewise linear function characterized by its breakpoints, where the slope of the function changes. I know there exists an algorithm with $O(n \log(n))$ complexity to find the breakpoints. https://www.sciencedirect.com/science/article/pii/0020019089901361

Question: Can the complexity be reduced if $m_i \geq 0$ for all $i$.


1 Answer 1


Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m_1 x + b_1 - m_2 x - b_2$ has the same sign as $(m_1 + M) x + b_1 - (m_2 + M) x - b_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints, in linear time, given the breakpoints for the linear functions $(m_i + M)x + b_i$.

Now let $M = \max (-m_i)$, which can be found in linear time. The functions $(m_i + M)x + b_i$ all satisfy your condition. Hence if you could solve your problem in $f(n)$, then you could solve the original problem in $f(n) + O(n)$. Therefore you need not expect a more efficient solution for your special case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.