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


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


quasi wrote: >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.
Ok, I see you amended your specification.
Now it makes more sense.
quasi

