Find minimal functions

Question

OK, here's the deal. I have a bunch of linear functions, a*x + b.

My goal is to answer the following question/query: What is the minimal function at x = q?

E.g.: If I have functions f(x) = 3*x + 2, g(x) = 5*x - 6 and h(x) = 2*x + 1, I will answer for e.g.:

• for x = 4, function h

• for x = 2, function g

• for x = 1, function g

My idea goes like this:

1. Sort the functions by the coefficient of x, in decreasing order.

2. Sort the queries in increasing order

3. Get rid of the parallel functions, keep the ones with the smallest constant term (e.g.: if I have f(x) = 2*x + 4 and g(x) = 2*x + 2, f(x) will never be smaller than g(x), so I don't need f(x)).

4. Right now I am on the interval from -inf to some real number, call it w1 and I know that on this interval, the function with the highest linear coefficient is the smallest

5. Find w1 by finding the smallest x1 s.t. f(x1) = g(x1) where f is my current function and g iterates through all other functions with a smaller linear coefficient, w1 = x1

6. Repeat as long as my query is in the interval (-inf, w1): output the current function, then proceed to the next query.

7. If I still have queries that needed to be answered, let the current function be the one that intersects my actual current function at x = w1, and instead of -inf put w1, repeat the same steps.

However, my implementation or idea is not fast enough. Is there anything that I didn't notice that may speed up my program?

Thank you in advance.

Answer 1

could you not just solve for their intersections, and store the greatest function for each interval in the domain?

edit- to elaborate, if you were to solve any pair of functions for x, then x represents the value where one of those two functions becomes greater than the other. There's going to be definable intervals where the minimal function is the same for all the values in the interval.

Here's a plot of your 3 example functions.

The intervals(with the corresponding minimal function) of this graph would be

(-∞, 7/3]     => 5x - 6
(7/3, ∞]      => 2x + 1

Now, at runtime, instead of "What is the minimal function at x = q" you simply do "What interval does q belong to".

And, if I'm not mistaken, if you have N linear functions, you would have at most N-1 intervals to store. And, there's specialized data structures that you can use to store and search intervals if you really have a lot of functions to analyze.