Query min value at x of many equations in the form |x-a| + b

Kind of unrelated to what I was doing, but I stumbled on this interesting data structure. I can't figure out a few details.

Suppose I have like N<10^5 equations in the form y = |x-a| + b, with 0 < x, a, b < 10^5. After O(N) preprocessing, for any x, I want to find the minimum value out of all these equations in constant time.

Here's what I have so far: add the functions one by one in increasing values of a, somehow find the intersection between the new function and the min existing function, then store intersections. The intersections can tell us what equation to use for the min. Then we can use binary search for log time queries, but since x<10^5, we can just go through all values and precompute the correct min value for each x

Visualization, where the black is the min values

https://stackoverflow.com/questions/65855935/query-min-value-at-x-of-many-equations-in-the-form-x-a-b January 23, 2021 at 01:07PM