On Thursday, July 11, 2013 2:11:21 PM UTC-7, Leon Aigret wrote: > The cost function SUM(y_i - y(x_i)) for the line y = a x + b becomes > SUM(y_i - a x_i - b) = N (y_mean - a x_mean - b), so minimizing this > function corresponds with maximizing a x_mean +b. Calculating x_mean > is O(N), but has to be done just once.
Carrying this one step further, minimizing the cost function is just maximizing a. The problem with this is that the cost is subject to y_i-y(x_i)>=0
> Actually, since a x_mean + b has the geometrical interpretation of > y-coordinate of the intersection of y = a x + b and x = x_mean, > repeated evaluation of that expression can be replaced by the > geometrical argument that the best line is the line with the highest > intersection point, which must (and can) be the point where the line > x = x_mean reaches the convex hull.
Can you explain what you mean by "the line with the highest intersection point"?