quasi
Posts:
10,305
Registered:
7/15/05


Re: How to find a bounding line?
Posted:
Jul 7, 2013 8:36 PM


ols6000 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 the only requirement is that y = ax + b is an upper bounding line, you can choose one of a,b arbitrarily. A value for the other parameter can then be easily found.
For example, choose b = 0. Then simply choose a as the maximum value of y_i/x_i, for i = 1..N.
As another example, choose a = 0. Then simply choose b as the maximum value of y_i for i = 1..N.
Thus, you probably want to specify additional conditions on the line y = ax + b, other than just an upper bounding line.
quasi

