LudovicoVan
Posts:
4,025
From:
London
Registered:
2/8/08


Re: How to find a bounding line?
Posted:
Jul 8, 2013 7:50 AM


"quasi" <quasi@null.set> wrote in message news:vqukt8huprh8hvhi21tmb47a29m41558kf@4ax.com... > ols6000 wrote: >>quasi wrote: >>> >>> Firstly, it's clear that if y = ax + b is an optimal bounding >>> line, then it must pass through one of the N points, otherwise >>> b can be increased [edit], contrary to minimality of the sum. >> >>I agree. >> >>> But in fact, I'll show that there is an optimal line which >>> passes through at least two of the N points, not just one. >> >>It seems likely, but I don't follow your proof. > > I looked at it again. I think my proof that there is an optimal > lower bounding line through at least two points is good. > > Based on that result, O(N^2) is automatic.
The problem is that any of those lines is a candidate solution, isn't it? The convex hull in this problem can be found in O(N) (points are sorted by their first coordinate, we just need a scan of all points). If M is the number of points of the convex hull, where M=N in the worst case, there are M1 candidates to check, N1 in the worst case. Moreover, for each candidate, we need recompute the cost function (right?), which amounts to a scan of at least N2 points. We end up with something like O(N+N^2). Is that what you had in mind?
That said, there is a lot of geometric structure in that set of points, yet, if there is any way not to do all that work, I am not seeing it...
Julio

