
Re: How to find a bounding line?
Posted:
Jul 8, 2013 7:18 AM


ols6000@sbcglobal.net wrote: > I have a N points (x_i, y_i). I want to find a bounding line y = ax + b, such that y_i  y(x_i) >= 0. x_i and y_i are positive integers; a, b and y are real,and x is an integer. > > y_i = i, and x_{i+1} > x_i for all i<N > > N is very large (100,000  1,000,000), so I'm looking for a method that is O(N) (or better). > > An ideas on how this line could be found, i e, how to determine a and b efficiently from the N data points?
If this can be restated as a 'find the convex hull of a finite set of points' problem, then the references here: https://en.wikipedia.org/wiki/Convex_hull_algorithms may be relevant.
 I think I am an Elephant, Behind another Elephant Behind /another/ Elephant who isn't really there.... A.A. Milne

