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,325
Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 7, 2013 9:45 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic 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
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.