On Wednesday, July 10, 2013 7:24:31 AM UTC-7, Leon Aigret wrote: > About the only thing not yet done in this thread is summarizing the > findings:
Here is a summary of where I think we are so far.
Leon Aigret says > The lower bound criterion turns out to be equivalent with the > requirement that the bounding line stays below, with just touching > allowed, the convex hull of the set of points.
This has not been proved. 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), 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.