
Re: How to find a bounding line?
Posted:
Jul 7, 2013 6:45 PM


<ols6000@sbcglobal.net> wrote in message news:331529483734432a82855961590107ef@googlegroups.com... >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?
you state N is two dimentional, then you have it as one dimentional ("for all i<N"). Which is it ?

