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


Re: How to find a bounding line?
Posted:
Jul 11, 2013 4:13 PM


"quasi" <quasi@null.set> wrote in message news:sv3ut81468r32190odno2jc1pnei0lmlit@4ax.com... > ols6000 wrote: > >>One further thing to keep in mind: a method in which you select >>the best of N1 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.
Julio
> 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?

