Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by

$f(x) = \max_i ( a_i + b_i x )$

We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:

$x = - \frac{a_i - a_j}{b_i - b_j}$

for $b_i\neq b_j$ and there are at most $n(n-1)/2$ such intersections. For large $n$ it may be impractical to manually check all possible points. Does there exist an efficient way of checking only a subset of the points, ideally one which completes in $O(n)$ rather than $O(n^2)$ time?

I'm thinking something along the lines of the simplex method, which moves from corner to corner of a convex set (the relevant set in this case being the area above the curve $f(x)$).

willindeed only use $O(n)$ steps, because your set has at most $n+1$ corners (there can’t be more than two on a particular line). Whether a generic LP solver (as indicated in Brian Borchers’ answer) will or will not be faster than a special-purpose simplex implementation is not clear to me. – Emil Jeřábek Apr 15 '11 at 18:59