Algorithm to find the lower envelope of set of piece-wise linear functions I am looking for an algorithm that finds the lower envelope of a set of continuous piece-wise linear functions.
E.g. given two functions $f(x)$ and $g(x)$ I want to find $h(x)$ as shown below:
$f(x)=\left\{\begin{array}{ll}
2x, & 0 \le x<5\\
10 ,& 5 \le x
\end{array}
\right.
$
$g(x)=\left\{\begin{array}{ll}
0.5x+5, & 0 \le x<20\\
15 ,& 20 \le x
\end{array}
\right.$
$h(x)=\left\{\begin{array}{ll}
2x, & 0 \le x<\frac{10}{3}\\
0.5x+5 ,& \frac{10}{3} \le x < 10 \\
10 ,& 10 \le x 
\end{array}
\right.$
My problem has a large number of piece-wise functions, with a variable numbers of pieces.
 A: The simplest algorithm which is better than brute force takes $O(Nm)$ time where $N$ is the total number of pieces (treated as line segments) and $m$ is the number of pieces that are part of the lower envelope. Start by finding the piece that starts the lowest at the left-most part of your argument range, and if there is a tie pick the piece that has the lowest slope. This is the first piece for your lower envelope. Compute the intersection points of this piece (line segment) with all other pieces. The earliest intersection point is where you switch to the next piece, where the next piece is the piece that intersected at the earliest intersection point (choosing the lowest slope if there is a tie for the earliest intersection point). Then your lower envelope is made up of the new piece starting at the intersection point. So now repeat the process, compute the intersection of the piece will all pieces, and choose the earliest intersection point after the previous intersection point you computed before. This is where you switch to the next new piece. And so forth.
If you want to speed this up, you can store intervals as 2-d points $(L,R)$ which give the x-coordinate of the left and right endpoints, stored in a range tree or a kd-tree, and when you want to compute intersections with a given interval you do a range query to find the intervals whose $(L,R)$ representations are in the range $(-\infty,R_0)\times(L_0,\infty)$ where $(L_0,R_0)$ is the representation of the interval you want to intersect (and $L_0$ can be the current intersection $x$-coordinate rather than the left-end point of the interval). The query can be answered in $O(\log N + k)$ time where $k$ is the number of intervals that satisfy the query. This can give you substantial speed-up because you skip all the intervals whose x-coordinates are outside the range of your query interval's x-coordinates.
