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 ]
 Leon Aigret Posts: 31 Registered: 12/2/12
Re: How to find a bounding line?
Posted: Jul 11, 2013 5:11 PM

On Thu, 11 Jul 2013 16:14:05 -0500, quasi <quasi@null.set> wrote:

>"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.

The cost function SUM(y_i - y(x_i)) for the line y = a x + b becomes
SUM(y_i - a x_i - b) = N (y_mean - a x_mean - b), so minimizing this
function corresponds with maximizing a x_mean +b. Calculating x_mean
is O(N), but has to be done just once.

Actually, since a x_mean + b has the geometrical interpretation of
y-coordinate of the intersection of y = a x + b and x = x_mean,
repeated evaluation of that expression can be replaced by the
geometrical argument that the best line is the line with the highest
intersection point, which must (and can) be the point where the line
x = x_mean reaches the convex hull.

Leon

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