"quasi" <email@example.com> wrote in message news:firstname.lastname@example.org... > ols6000 wrote: > >>One further thing to keep in mind: a method in which you select >>the best of N-1 lines is O(N^2), because calculation of the sum >>for each line is O(N). That means such a method isn't practical. > > Good point. > > The most efficient algorithm proposed so far has complexity O(N) > _times_ the complexity of a distance sum calculation. > > However, a distance sum calculation by its very nature is O(N). > so if each one of the distance sum calculations has to be done > separately, and if each one is O(N), then, as you indicate, the > whole task is O(N^2). > > It seems unlikely that you can do better.
As already noted, we can indeed do better, namely O(N+N), as there is no need to recalculate the cost function from scratch at each step.
> But do you now at least acknowledge my previous claim that there > is an optimal bounding line which passes through two consecutive > points of the convex hull?