quasi
Posts:
11,740
Registered:
7/15/05


Re: How to find a bounding line?
Posted:
Jul 8, 2013 7:43 AM


Peter Percival 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 this can be restated as a 'find the convex hull of a >finite set of points' problem, then the references here: > >https://en.wikipedia.org/wiki/Convex_hull_algorithms > >may be relevant.
Definitely relevant.
Assuming you already have the convex hull, finding the optimal lower bounding line is just O(N) from there, since it's sufficient to evaluate the distance sums for lines determined by consecutive points of the convex hull, and then choose a line whose distance sum is least.
Based on the Wiki link above, the most promising approach seems to be Graham's method. Quoting from the link:
"A slightly more sophisticated, but much more efficient algorithm, published by Ronald Graham in 1972. If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(n) time."
Since the OP's data is already sorted by the xcoordinates, (and in fact, also by the ycoordinates) Graham's method takes O(N) time, and hence the whole job takes O(N) time.
quasi

