Date: Jul 7, 2013 6:45 PM
Author: Scott Berg
Subject: Re: How to find a bounding line?

<> wrote in message
>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?

you state N is two dimentional, then you have it as one dimentional ("for
all i<N").
Which is it ?