>Only the fact that a "best" bounding line must pass through at >least one point has been shown (by quasi). > >If it turns out to be true that said line must pass through at >least two points, then we have an O(n^2) method, which is too >slow for practical use. > >The convex hull may be found in O(n) time, given that the data >is already sorted, but even if the optimum line(s) pass through > two points on the hull (and this hasn't yet been proved),
I claim it _has_ been proved.
>the method is still O(n^2). > >The hypothesis that an optimum line must pass through two >neighboring points of the original data is incorrect, as shown >by counter-example. > >It may be that an optimum line must pass through two >neighboring points of the convex hull, but this has not been >proved.
It's a triviality (draw a picture).
If a bounding line passes through two points of the convex hull it must pass through two _consecutive_ points of the convex hull.