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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ 1. May we assume the $f_i$'s are continuous? 2. What approaches have you considered? What's the best algorithm you can find, and what is its running time? Have you looked at segment trees, interval trees, and such? Have you considered a sweep line algorithm (i.e., left-to-right linear scan)? Have you looked at en.wikipedia.org/wiki/Line_segment_intersection? $\endgroup$– D.W. ♦Jan 6, 2016 at 7:41
-
$\begingroup$ 1. Yes, all the $f_i$'s are continuous. 2. I thought some sort of sweep line algorithm but didn't have a concrete procedure. (I didn't even know such a name since I have zero CS algorithm training.) $\endgroup$– William ZhangJan 6, 2016 at 14:49
-
$\begingroup$ OK, cool! Those are some standard tools/techniques for this space -- and they make for fun reading. $\endgroup$– D.W. ♦Jan 6, 2016 at 18:07
-
$\begingroup$ I guess the solution depends on how the $f_i$ are given. $\endgroup$– Raphael ♦Jan 6, 2016 at 18:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)$.