Woody
Posts:
44
Registered:
7/29/09


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


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?

