Intersection of $2$ piecewise linear curves

Question

I want to create a low complexity algorithm to find a point of intersection of $2$ piecewise linear curves. One curve is monotonic decreasing and the other in monotonic increasing. Any suggestion on which method to use to get a low complexity algorithm?

Answer 1

First, create a set of all x-values where either curve changes slope. If one curve is monotonically increasing and the other is monotonically decreasing, you can jump from each x-value in the set to another starting from the smallest and increasing and calculate the y-value of each curve at that point. Once you reach an x-value where the y-value of the monotonically increasing curve is larger than the y-value of the monotonically decreasing curve, you can find the slope-intercept forms of each of the curves where they intersect by using their current slopes and the y-values at the point you stopped at. Then, you just plug their slopes and y-intercepts into $x=\frac{b_{decreasing}-b_{increasing}}{m_{increasing}-m_{decreasing}}$ to find the x-value at which they intersect. You can then plug that value of x into either function to find the point of intersection. You may also want to search up "coordinate compression", which deals with a very similar topic in coding problems.

Answer 2

Hints:

There is an easy solution with linear complexity $O(n+m)$ (assuming that the pieces are sorted by increasing abscissa): perform a merge operation of the two lists of bounds, and at every value in one list, check if the value in the other list (obtained by linear interpolation) crosses.

But there is a faster way by dichotomy: choose the middle abscissa in one list and find the corresponding pair of abscissas that straddle it in the other list, by means of a dichotomic search. The sign of the difference of ordinates tells you if the intersection is on the left of on the right. Then repeat the process in the left or right halve. This leads to a complexity $O(\log(n)\log(m))$.