quasi wrote: >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,
otherwise b can be increased,
>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 point-slope 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 N-1 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 N-1 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).