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

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 ]
quasi

Posts: 10,305
Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 7, 2013 10:08 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

quasi wrote:
>ols6000 wrote:
>>
>>I forgot to mention that I am looking for the "best" bounding
>>line, in the sense that SUM(y_i - y(x_i)) is minimal (but
>>each y_i - y(x_i) is >=0).

>
>With that additional restriction, I see a fairly natural
>approach ...
>
>Firstly, it's clear that if y = ax + b is an optimal bounding
>line, then it must pass through one of the N points,
>otherwise b can be reduced,


I meant:

otherwise b can be increased,

>contrary to minimality of the sum.
>
>But in fact, I'll show that there is an optimal line which passes
>through at least two of the N points, not just one.
>
>To show that, assume an optimal line L with slope a passes through
>the point (x_k,y_k).
>
>By the point-slope formula, the line has the equation
>
> y - y_k = a*(x - x_k)
>
>or equivalently,
>
> y = a*x + (y_k - a*x_k)
>
>Let s = SUM(y_i - y(x_i)).
>
>Since L is an optimal bounding line, s is minimal, hence a change
>in the value of a, if it doesn't break the bounding condition,
>cannot decrease the sum.
>
>But the sum s is at most linear as a function of a.
>
>Case (1): s is degree 1 as function of a.
>
>If L does not pass through any of the other N-1 points, a
>sufficiently small positive or negative change in a will decrease
>the value of s, while still yielding a bounding line, contrary
>to the optimality of L. Hence in case (1), the line L must pass
>through at least two of the N points.
>
>Case (2): s is constant as function of a.
>
>Then any change in a will leave s unchanged, so we can change
>a so that the line is still a bounding line, but now
>also passes through at least one of the other N-1 points.
>Hence in case (2), the line L can be chosen so as to pass
>through at least two of the N points.
>
>Thus, in both cases there is an optimal bounding line which
>passes through at least two of the N points.
>
>Next, we get a kind of a convex hull for the piecewise linear
>function determined by the vertices (x_i,y_i).
>
>To do this, make one pass through the list of N points, removing
>from the list any point (x_i,y_i) which is such that it is above
>or on the line through its two neighbors. Once a point is dropped,
>it's no longer a neighbor. Neighbors of a currently live point
>are the live points with closest left and right x values.
>
>After one such removal pass, the piecewise function through
>the remaining vertices is a convex function.
>
>Any lower bounding line passing through at least two points of
>the original N point set also passes through two points of
>the new set. But any lower bounding line which point passes
>through two points of the new set must (due to convexity) pass
>through two consecutive points of the new set.
>
>Thus, it suffices to compute s (using all N points) for each
>line determined by two consecutive points of the new set.
>
>The algorithm as described above is O(N).


quasi


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.