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 ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 11, 2013 4:36 PM

"Julio Di Egidio wrote:
>"quasi wrote:
>> 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.

I must have missed that.

If you can avoid recalculations of the cost function at each
step, then, as you indicate, the whole task is just O(N), and
thus, ols6000 is potentially back in business.

quasi

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