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 8, 2013 1:35 AM

quasi wrote:
>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).

The following is simpler:

With a slight adjustment of my previous argument, one of the
N-1 lines through the points (x_i,y_i) and (x_(i+1),y_(i+1))
for i = 1..(N-1) is an optimal lower bounding line. So for
each of those N-1 lines, first check to make sure the line
is a lower bounding line, and of those lines that qualify,
choose one with the least value of s.

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