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

<ols6000@sbcglobal.net> wrote in message

news:33152948-3734-432a-8285-5961590107ef@googlegroups.com...

>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 ?