Let $f_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define $$g(x) = \min_{1\leq i\leq n} f_i(x).$$ Clearly, $g(x)$ is also a piecewise linear function. What would be a good approach to compute all the pieces? In other words, it's clear that $g(x)$ can be represented as$$g(x) = c_k + d_k x,\quad \text{for } x\in[e_k,e_{k+1}),$$for some choice of $(c_k,d_k,e_k)$'s.  How do I compute these $(c_k,d_k,e_k)$'s in an efficient way, given the $f_i$'s?
Efficient algorithm to compute the minimum of multiple piecewise linear functions
algorithms;computational geometry;efficiency;numerical algorithms
This is basically an instance of the line segment intersection problem.  One standard approach is to use a sweep line algorithm.  For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.At each iteration of the algorithm, we have some value of $x$, and we calculate what is the next largest value of $x$ where something interesting happens.  Here, something interesting is either (1) two pieces intersect each other at a point, or (2) we reach the end of one of the current pieces.  Then we advance $x$ to this next value.At each iteration, we keep track of which pieces are currently active (i.e., $x$ is within the domain of that piece) and the order of the pieces, ordered by their $y$-value for that particular value of $x$.  Store them in sorted order, sorted by $y$-value.All of the interesting bit is in how we determine the next largest value of $x$ where something interesting happens.  Fortunately, this is easy.  For each pair of adjacent active pieces (adjacent in their sorted order), we can find whether they intersect and where, and if it corresponds to a larger value of $x$, add it to a priority queue.  Also, for each active piece, we can add its right endpoint (the largest value of $x$ in its domain) to the priority queue.  Then finding the next interesting value of $x$ amounts to an ExtractMin operation on the priority queue.  Also, when you move to the next largest interesting value of $x$, it's easy to update the set of active pieces and maintain them in sorted order.Let $n$ denote the total number of pieces among the $f_i$'s, and $k$ the total number of intersections between pieces.  Then each iteration can be implemented in $O(\lg n)$ time, and the number of iterations can be upper bounded by $O(n+k)$, so the running time will be $O((n+k) \lg n)$.