Determining which linear function is largest I have a collection of linear functions of form $y_i= m_ix + b_i$ for positive integers $m,b,x$. I am trying to efficiently determine which equation (i.e. which $i$) corresponds to the largest $y_i$ given some $x$, for many $x$ (it is easy enough to do this for a single $x$, just update the equations and sort, but this is over many $x$ so this is no longer appropriate).
For example if $y_1 = 3x + 7$ and $y_2 = 5x + 4$, if $x=1$, then $y_1 = 10$ and $y_2 = 9$, so $i=1$ is maximal. 
But when $x=2$, then $y_1 = 13$ and $y_2 = 14$, so now $i=2$ is maximal.
One important thing I can note is that once one equation meets/surpasses another, it will always be larger.
I would ask this on StackOverflow but since it's math related they'd just tell me to come post it here anyway.
 A: Keep track of the line $y_1$ with the largest $b$ value. Say it has slope $m_1$. Then consider other lines with larger slopes. Calculate their intersections with line $y_1$.
Find the line whose intersection with $y_1$ corresponds to the lowest $x$-value. Call this line $y_2$. Instead of keeping track of $y_1$, keep track of $y_2$ and do the same thing as above. Find all lines with larger slopes, calculate their intersection points, etc.
Keep doing this until you've exhausted your collection of lines.
You should then have a list of the largest lines for each value of $x$. Originally, the line with the highest $y$-intercept was chosen, but as other lines overtook it we had new lines. If we were to graph the segments of the line we kept track of it would look somewhat like a jagged parabola.
For a given $x$ you just find the line which was maximal at the given time.
A: You did not specify whether the lines are given before all the queries, which would be much easier than if you can intersperse insertions and deletions of the lines among the queries. In both cases, what you would need is the convex region bounded below by all the lines. If all the lines are given in advance, it should not be hard to figure out how to obtain the region in $O(n\cdot\log(n))$ time for $n$ lines. However, if you have a dynamically changing set of lines, it would be much harder.
To get the $O(n\cdot\log(n))$ time complexity as claimed, sort by gradient and do a single pass using a stack, which takes amortized constant time per line because once a line is popped off the stack it is never pushed back on.
