
Re: How to find a bounding line?
Posted:
Jul 10, 2013 10:24 AM


On Mon, 8 Jul 2013 10:25:33 0700 (PDT), ols6000@sbcglobal.net wrote:
>On Monday, July 8, 2013 6:41:18 AM UTC7, 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 it is no longer necessary, once a hull point has been listed with x > x_mean, to add new points 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

