LudovicoVan
Posts:
3,612
From:
London
Registered:
2/8/08


Re: How to find a bounding line?
Posted:
Jul 8, 2013 9:15 AM


"Julio Di Egidio" <julio@diegidio.name> wrote in message news:kre8of$1hd$1@dontemail.me... > "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.
In fact, no: at the first scan we can already reduce the cost function to a function of a and b only, so recomputing the cost function is just a matter of plugging in values for a and b. The complexity would be O(N+N).
Could better be done? E.g. do we really need to check all candidates?
Julio
> 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...

