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 ]
Leon Aigret

Posts: 31
Registered: 12/2/12
Re: How to find a bounding line?
Posted: Jul 10, 2013 10:14 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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