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)$).
Best Answer
Looking at a figure one is lead to the following algorithm which traces out the graph of $f$:
One may assume $a_1< a_2 < \ldots < a_n$. If $0 < a_1$ or $a_n < 0$ then $m:=\min_x f(x)=-\infty$. Otherwise for $x$ large negative one has $f(x)=a_1 x + b_1$ and for $x$ large positive one has $f(x)=a_n x+b_n$. Therefore put $x_1:=-\infty$, $j_1:=1$ and for $k\geq1$ define recursively $$ r_i := {b_{j_k}-b_i\over a_i-a_{j_k}} \ (j_k < i \leq n),\quad x_{k+1}:=\min_{j_k < i \leq n}\ r_i\ ,\quad j_{k+1}:=\arg\min_{j_k < i \leq n} r_i\ .$$ When for the first time $a_{j_{k+1}}\geq0$ the minimum is found: One has $m=a_{j_k}x_{k+1}+b_{j_k}$.
As a bonus I propose the following algorithm which seems more sophisticated and is maybe faster:
Put $g_i(x):=a_i x+ b_i$ and denote by $g_i\wedge g_j$ the point of intersection of the two graphs. Assume for simplicity $ a_1 < \ldots a_s<0 < a_{s+1} < \ldots < a_n$. Then apply in succession