Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: How to find a bounding line?
Replies: 39   Last Post: Jul 12, 2013 5:39 AM

 Messages: [ Previous | Next ]
 LudovicoVan Posts: 4,165 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 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
>
> 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?

Date Subject Author
7/7/13 Woody
7/7/13 Scott Berg
7/7/13 Peter Percival
7/7/13 Woody
7/7/13 quasi
7/7/13 quasi
7/8/13 quasi
7/8/13 Woody
7/8/13 quasi
7/8/13 LudovicoVan
7/8/13 LudovicoVan
7/10/13 Woody
7/10/13 quasi
7/8/13 Leon Aigret
7/8/13 Woody
7/10/13 Leon Aigret
7/10/13 Leon Aigret
7/10/13 Woody
7/10/13 RGVickson@shaw.ca
7/10/13 Woody
7/10/13 quasi
7/7/13 quasi
7/7/13 quasi
7/7/13 quasi
7/8/13 William Elliot
7/8/13 Peter Percival
7/8/13 quasi
7/11/13 Woody
7/11/13 quasi
7/11/13 LudovicoVan
7/11/13 quasi
7/11/13 Leon Aigret
7/11/13 Woody
7/11/13 Leon Aigret
7/12/13 Woody
7/12/13 Leon Aigret
7/11/13 Woody
7/12/13 quasi
7/12/13 Woody
7/12/13 quasi