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



Efficient algorithm for finding the minima of a piecewise linear function
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


1. Put $l:=1$, $\ r:=n$.
2. Put $(\xi,\eta):= g\_l\wedge g\_r\ $.
3. If $l=s$ and $r=s+1$, goto 7.
4. Let $\tau:=\max\_{l < i < r}\ g\_i(\xi)\ ,\quad p:=\arg\max\_{l < i < r}\ g\_i(\xi).$
5. If $\tau\leq \eta$ goto 7.
6. If $p\leq s$ put $l:=p$, else put $r:=p$; then goto 2.
7. $m=\eta$.


