quasi wrote: >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, > >I meant: > >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).
The following is simpler:
With a slight adjustment of my previous argument, one of the N-1 lines through the points (x_i,y_i) and (x_(i+1),y_(i+1)) for i = 1..(N-1) is an optimal lower bounding line. So for each of those N-1 lines, first check to make sure the line is a lower bounding line, and of those lines that qualify, choose one with the least value of s.