quasi
Posts:
12,047
Registered:
7/15/05


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


quasi wrote: >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.
Also, now that I look more carefully, it appears you want a lower bounding line, not an upper bounding line.
No problem.
I definitely see an O(N^2) approach, but in fact, I think I see an O(N) approach. If my idea survives further scrutiny, I'll post it in my next reply.
quasi

