# Upper (or lower) envelope of some linear functions

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$$.

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.