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 ]
 Leon Aigret Posts: 31 Registered: 12/2/12
Re: How to find a bounding line?
Posted: Jul 10, 2013 10:14 AM

On Mon, 8 Jul 2013 10:25:33 -0700 (PDT), ols6000@sbcglobal.net wrote:

>On Monday, July 8, 2013 6:41:18 AM UTC-7, Leon Aigret wrote:
>> So you are looking for the minimum of y_mean - a x_mean - b ?
>
>Yes, subject to each y_i - y(x_i) being >=0 (the "lower bound" criterion).

About the only thing not yet done in this thread is summarizing the
findings:

The lower bound criterion turns out to be equivalent with the
requirement that the bounding line stays below, with just touching
allowed, the convex hull of the set of points.
The best line y = a x + b is the line with the highest value of
a x_mean + b. Obviously, that must be the "tangent" to the convex hull
in the lowest point of the intersection of the convex hull with the
line x = x_mean. The solution may not be unique if that intersection
point happens to be one of the original data points.

As has been pointed out, Wikipedia describes a number of convex hull
finding methods. For the already sorted data in this problem, the
monotone chain method might be useful. Details can be found at
https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Only the line segment of the lower hull that crosses the line x =
x_mean is needed, so the determination of the upper hull can be
skipped, and is it no longer necessary, once a hull point has been
listed with x > x_mean, to add a new point to the list, except
immediately after removing one or more points. After completion, the
last two points on the list lie on the required bounding line.

Leon

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