quasi
Posts:
10,232
Registered:
7/15/05


Re: How to find a bounding line?
Posted:
Jul 10, 2013 5:13 PM


ols6000 wrote: > >This has not been proved.
I think it has.
>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 counterexample. > >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.
Thus, the task is O(N).
quasi

