"Julio Di Egidio" <email@example.com> wrote in message news:firstname.lastname@example.org... > "quasi" <email@example.com> wrote in message > news:firstname.lastname@example.org... >> 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 , 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 M-1 candidates to check, N-1 in the worst case. Moreover, for each > candidate, we need re-compute the cost function (right?), which amounts to > a scan of at least N-2 points.
In fact, no: at the first scan we can already reduce the cost function to a function of a and b only, so re-computing 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?
> 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...