ols6000 wrote: >quasi wrote: >> >> 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 = 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 > >This is not correct. A small change in a can either increase >or decrease s, depending on the values x_i.
Since s is degree 1 in a, either a positive change in a will decrease the value of s, or a negative change in a will decrease the value of s. One change or the other (not both) will decrease the value of s.
>Whether L passes through any of the other points is irrelevant.
The relevance is that if L is a lower bounding line which passes through only one of the N points, say (x_k,y_k), then the line can be rotated slightly in either direction (clockwise or counterclockwise) through the point (x_k,y_k) and will still be a lower bounding line.
Recalling that a denotes the slope of the line through the point (x_k,y_k), a clockwise rotation will decrease the value of a, and a counterclockwise rotation will increase the value of a.
One of those rotations will decrease the value of s.