Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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

>
>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
Read How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
Scott Berg
7/7/13
Read Re: How to find a bounding line?
Peter Percival
7/7/13
Read Re: How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Woody
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Leon Aigret
7/8/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
RGVickson@shaw.ca
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
William Elliot
7/8/13
Read Re: How to find a bounding line?
Peter Percival
7/8/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
LudovicoVan
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.