Search All of the Math Forum:

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

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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 quasi Posts: 12,052 Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 7, 2013 9:45 PM
 Plain Text Reply

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

© The Math Forum at NCTM 1994-2017. All Rights Reserved.