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.

Answer 2

If I understood correctly, your solution is to do some pre-processing to all your functions so that the domain of x is split into ranges, and in every such a range you know what's the minimal function.

There're actually two phases: the "preparation" and the "querying" (where given a specific x you give the result).

What's your bottleneck?

Naturally for the "querying" phase to be fast you should organize your ranges in a kind of a sorted array, so that you can find the range enclosing the given x by a median search (or similar) in a logarithmic time. If this is what you did and still this isn't fast enough - consider code-level optimizations, because from the algorithmic point of view this seems to be the most optimal solution.

If your bottleneck is the "preparation" phase - here there're opportunities for optimizations. As I understand, you find intersections of all the pairs of your functions (after getting rid of parallel ones). And this is not really necessary.

Consider the following. First you sort all your functions by their coefficient (higher coefficients are at the beginning). Get rid of parallel functions. Next build the array of the ranges, while iterating through your functions.

Since the current function has the lowest coefficient (among those that have already been analyzed) - the current function will be the smallest one as x goes to infinity. So that its range should be from some x0 to infinity. Find that x0. Take the last range from the array (belonging to the previously-processed function), and find x0 - the intersection of that function with the current one. The former range shrinks up to x0. If that range becomes invalid (range start greater than x0) - means that that function is totally obscured. In such a case - remove that range, and repeat the procedure.

To make things more clear I'll write a pseudo-code:

rangeArr is an array of pairs F,X, whereas F is the function description, and X is the start of the function range. The end of the function range is considered the start of the next range, and the end of the last function range is +infinity.

for each F sorted by coefficient
{
    double x0;

    while (true)
    {
        if (rangeArr is empty)
        {
            x0 = -inf;
            break;
        }

        FPrev = rangeArr.back().F;
        xPrev = rangeArr.back().X;

        x0 = IntersectionOf(F, FPrev);

        if (x0 > xPrev)
            break;

        rangeArr.DeleteLastRange();
    }

    rangeArr.InsertRange(F, x0);
}