I have an array of tuples (a, b) with a > 0 and b > 0.
Each tuple represents a function f such that f(x, a, b) = a * min(b, x).
Is there a known algorithm for a given x to find which tuple returns the maximum value ?
I don't want to evaluate each function to check the maximum, because I will query this array arbitrary number of times for different x.
Example:
array = [ (1, 10), (2, 3) ]
x < 6 -> choose (2, 3)
x = 6 (intersection point) -> either (1, 10) or (2, 3) doesn't matter
x > 6 -> choose (1, 10)
So the problem is that these tuples can be either sorted by a or by b. But there can be a lot of intersection points between them (if we visualize them as graphs). So I want to avoid any O(n^2) sorting algorithm to check for certain ranges of x which is the best function. I mean I don't want to compare each function with all the others to find from which point x' (intersection point) and on I should choose one over the other.
Assuming a's, b's and queried x's are always nonnegative, each query can be done in O(log(n)) time after an O(n*log(n)) preprocessing step:
The preprocessing step eliminates such functions that are strictly dominated by others. For example, (5, 10) is larger than (1, 1) for every x. (So, if there is (5, 10) in the array, then we can remove (1, 1) because it will never be the maximum for any x.)
Here is the general condition: A function (a, b) is larger than (c, d) for every x if and only if c > a and (c*d > a*b). (This is easy to prove.)
Now, what we want to do is to remove such functions (a, b) for which there exists a (c, d) such that c > a and (c*d > a*b). This can be done in O(n*log(n)) time:
1 - Sort tuples lexicographically. What I mean by lexicographically is first compare their first coordinates, and if they are equal, then compare the second ones. For example, a sorted array might look like this:
(1, 5)
(1, 17)
(2, 9)
(4, 3)
(4, 4)
2 - Iterate over the sorted array in the reverse order and keep track of the largest value of a*b that you encountered so far. Let's call this value M. Now, assume the element that we are processing in the loop is (a, b). If a*b < M, we remove this element. Because for some (c, d) that we processed earlier, both c > a and c*d > a*b, and thus (a, b) is useless. After this step, the example array will become:
(2, 9)
(4, 4)
(4, 3) was deleted because it was dominated by (4, 4). (1, 17) and (1, 5) were deleted because they are dominated by (2, 9).
Once we get rid of all the functions that are never the maximum for any x, the graph of the remaining ones will look like this.
As seen in the graph, every function is the maximum from the point where it intersects with the one before to the point where it intersects with the one after. For the example above, (4, 4) and (2, 9) intersect at x = 8. So (4, 4) is the maximum until x = 8, and after that point, (2, 9) is the maximum.
We want to calculate the points where consecutive functions in the array intersect, so that for a given x, we can binary-search on these points to find which function returns the maximum value.
