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 7, 2013 10:08 PM

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