Implementing piecewise linear functions

Question

I need to implement piecewise linear functions (this is not homework, it is for my own personal project). However, I have been having difficulties to get it right. Below, I describe the characteristics of the function, operations, and what I have tried so far.

Function: It is defined by linear segments. It may be discontinuous, and some segments may actually be points rather than lines. The function can be any mix of increasing or decreasing parts. The domain is completely bounded by a box with $x \in [0,M]$ and $y \in [0,M]$. The maximum value $M$ is always defined (e.g., never $\infty$).

Operations: The operations I need to perform are fairily simple in mathematical terms. I need:

1. Shift in $x$ and $y$ (easy)
2. Shrink/expand pieces (always at the end or start of the function, never in the middle)
3. Take the maximum between two piecewise linear functions $f(x)$ and $g(x)$ considering that all pieces are within the domains of the box ($[0,M]$) but the actual domain of the functions may not be the same (this has been tricky!)

What I have tried: So far I tried to implement the function as a series of linear pieces defined by their starting starting $(x_0,y_0)$ and ending ($x_1,y_1)$ coordinates. A function then is simply an array of such pieces. However, defining the maximum operation has been quite difficult for me, specially when there are discontinuities and the domain of the two functions $f$ and $g$ are different.

I know this may look more like a "help me with my code" question, but all I wanted was some guides in how to better implement such functions and operations. For example, is my current strategy good? Is there a description of an algorithm to take the maximum of two functions somewhere in the internet? I have tried Stack, Git, and Googling, but have not found any good result to help me with that. I guess either it is too easy and I just don't see it, or it is too obscure and few people do it.

NOTE: I really don't care about operation complexity right now. As long as it is polynomial it is good for me.

Answer 1

A similar question has been asked before, that may answer your question, here. Quoting the answer:

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.

So, in some sense it is a matter of proper abstraction: you need to implement a function

 something_interesting_happens(real x, function f1, function f2)

the function should return, given an x-value x, the next x-value where either an intersection occurs or the start or end of a line segment occurs. With this functionality out of the way, to return your maximum function, you just iterate over all the interesting x-values, starting from 0 and repeatedly using something_interesting_happens to get the next interesting x-value. It is a bit simpler for you as you are looking to only maximize two functions, and in the above quote they consider maximizing $n$ functions.

The final issue is that you need to settle on a representation for your piecewise linear functions. As plop points out in the comments, your current representation has an issue: it can't represent discontinuous functions.

Here's one possibility, for simplicity:

• Define a piece to be either an open line segment, represented by a pair of points $(x_1, y_1), (x_2, y_2)$, or a single point, represented by $(x_1, y_1)$. This gives you sufficient expressiveness to have both closed and open line segments, without worrying about representing open and closed line segments separately. In particular, a closed line segment will be an open line segment, plus points at both of the endpoints.

• It will be probably useful to have some functions on pieces, such as:

  intersect(piece p1, piece p2)
  

  to indicate if two pieces intersect in the $x$-values they consider, and

  less-than(piece p1, piece p2)
  

  which means that p1 and p2 don't intersect, and p1 is before p2.

• Represent a piecewise linear function by a (possibly empty) sequence of pieces. The pieces should be sorted, so that less-than(p1, p2) holds for all pieces in the list p1 and p2 where p1 occurs before than p1.

Answer 2

Your representation is fine. Store the pieces in sorted order, sorted by their $x$-coordinate. The first two operations are straightforward to implement. Computing the maximum takes a little more work but can be implemented in linear time. Basically, we are merging two sorted lists.

Let $P_1,\dots,P_m$ be the interval of $x$-coordinates of the pieces of $f(x)$ (in sorted order, leftmost to rightmost) and $Q_1,\dots,Q_n$ be the interval of $x$-coordinates of the pieces of $g(x)$ (in sorted order). Then you can do a case analysis based on $P_1$ and $Q_1$:

• If $P_1$ is wholly to the left of $Q_1$, then you can output $P_1$, discard it, and recurse on $P_2,\dots,P_m$ and $Q_1,\dots,Q_m$.

• By symmetry, if $Q_1$ is wholly to the left of $P_1$, then you can output $Q_1$, discard it, and recurse on $P_1,\dots,P_m$ and $Q_2,\dots,Q_m$.

• Finally, suppose $P_1,Q_1$ overlap. Suppose the left end of $P_1$ is to the left of the left end of $Q_1$. Then you can split $P_1$ into two intervals, one that is wholly to the left of $Q_1$ and one that is the intersection of $P_1$ and $Q_1$, and split $Q_1$ into two intervals, one that the intersection of $P_1$ and $Q_1$ and one that is wholly to the right of $P_1$. Now throw out the one wholly to the left of $Q_1$, take the maximum over the intersection, throw out $P_1$, replace $Q_1$ with the part to the right of the intersection, and recurse.

In each step you remove one of the intervals and recurse. This is tail-recursive so it can easily be converted to an iterative algorithm. Each step takes $O(1)$ time, so the total running time will be linear in the number of pieces.

Another way to view this: obtain a sorted list of the $x$-coordinates of the endpoints of all of the pieces (including both the pieces of $f(x)$ and the pieces of $g(x)$). This can be obtained in linear time by merging the sorted list associated with $f(x)$ and the sorted list associated with $g(x)$. Now each pair of adjacent $x$-coordinates corresponds to one piece of $f(x)$ and one piece of $g(x)$ (you can keep track of which pieces those are as you merge the lists). Then, you can easily compute the max of those two pieces over that range.

To compute the max of two pieces over a common range, you just take the intersection of those two line segments if the intersection is in the range, then the max has one piece to the left of the intersection and one to the right; otherwise the max is one of two original pieces.