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.