quasi
Posts:
12,052
Registered:
7/15/05


Re: How to find a bounding line?
Posted:
Jul 7, 2013 9:45 PM


ols6000 wrote: > >I forgot to mention that I am looking for the "best" bounding >line, in the sense that SUM(y_i  y(x_i)) is minimal (but >each y_i  y(x_i) is >=0).
With that additional restriction, I see a fairly natural approach ...
Firstly, it's clear that if y = ax + b is an optimal bounding line, then it must pass through one of the N points, otherwise b can be reduced, contrary to minimality of the sum.
But in fact, I'll show that there is an optimal line which passes through at least two of the N points, not just one.
To show that, assume an optimal line L with slope a passes through the point (x_k,y_k).
By the pointslope formula, the line has the equation y  y_k = a*(x  x_k)
or equivalently,
y = a*x + (y_k  a*x_k)
Let s = SUM(y_i  y(x_i)).
Since L is an optimal bounding line, s is minimal, hence a change in the value of a, if it doesn't break the bounding condition, cannot decrease the sum.
But the sum s is at most linear as a function of a.
Case (1): s is degree 1 as function of a.
If L does not pass through any of the other N1 points, a sufficiently small positive or negative change in a will decrease the value of s, while still yielding a bounding line, contrary to the optimality of L. Hence in case (1), the line L must pass through at least two of the N points.
Case (2): s is constant as function of a.
Then any change in a will leave s unchanged, so we can change a so that the line is still a bounding line, but now also passes through at least one of the other N1 points. Hence in case (2), the line L can be chosen so as to pass through at least two of the N points.
Thus, in both cases there is an optimal bounding line which passes through at least two of the N points.
Next, we get a kind of a convex hull for the piecewise linear function determined by the vertices (x_i,y_i).
To do this, make one pass through the list of N points, removing from the list any point (x_i,y_i) which is such that it is above or on the line through its two neighbors. Once a point is dropped, it's no longer a neighbor. Neighbors of a currently live point are the live points with closest left and right x values.
After one such removal pass, the piecewise function through the remaining vertices is a convex function.
Any lower bounding line passing through at least two points of the original N point set also passes through two points of the new set. But any lower bounding line which point passes through two points of the new set must (due to convexity) pass through two consecutive points of the new set.
Thus, it suffices to compute s (using all N points) for each line determined by two consecutive points of the new set.
The algorithm as described above is O(N).
quasi

