
Re: How to find a bounding line?
Posted:
Jul 8, 2013 3:14 AM


On Sun, 7 Jul 2013, ols6000@sbcglobal.net 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).
Why does x have to be an integer? Is't it a variable over the xaxis?
S = { (a1,1),.. (ak,k) } for j = 1,.. k1, 0 < aj < a_(j+1) for j = 1,.. k, aj in N, y(aj) <= j y(x) = rx + s; r,s in R
Find r,s in R for which sum(j=1,k) (j  y(aj)) is a minimum. Since sum(j=1,k) (j  y(aj)) = k(k+1)/2  sum(j=1,k) y(aj), the problem becomes find r,s in R for which sum(j=1,k) y(aj) is a maximum. with the constraints for j = 1,.. k, r.aj + s <= j.
s = sum(j=1,k) y(aj) = r.sum(j=1,k) aj + ks
Since r.a1 + s <= 1, to maximize s, set r.a1 + s = 1. Thus s = 1  r.a1. Let L1 be the horizontal line y = 1 and for j = 2,.. k draw a line Lj from (a1,1) to (aj,j). Let r be the minimal slope of all the lines, L2,.. Lk. Whence, y(x) = r(x  a1) + 1 is the line you want.
> An ideas on how this line could be found, i e, how to determine a and b > efficiently from the N data points?

