Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: How to find a bounding line?
Replies: 39   Last Post: Jul 12, 2013 5:39 AM

 Messages: [ Previous | Next ]
 quasi Posts: 12,067 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
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 x-coordinates,
(and in fact, also by the y-coordinates) Graham's method
takes O(N) time, and hence the whole job takes O(N) time.

quasi

Date Subject Author
7/7/13 Woody
7/7/13 Scott Berg
7/7/13 Peter Percival
7/7/13 Woody
7/7/13 quasi
7/7/13 quasi
7/8/13 quasi
7/8/13 Woody
7/8/13 quasi
7/8/13 LudovicoVan
7/8/13 LudovicoVan
7/10/13 Woody
7/10/13 quasi
7/8/13 Leon Aigret
7/8/13 Woody
7/10/13 Leon Aigret
7/10/13 Leon Aigret
7/10/13 Woody
7/10/13 RGVickson@shaw.ca
7/10/13 Woody
7/10/13 quasi
7/7/13 quasi
7/7/13 quasi
7/7/13 quasi
7/8/13 William Elliot
7/8/13 Peter Percival
7/8/13 quasi
7/11/13 Woody
7/11/13 quasi
7/11/13 LudovicoVan
7/11/13 quasi
7/11/13 Leon Aigret
7/11/13 Woody
7/11/13 Leon Aigret
7/12/13 Woody
7/12/13 Leon Aigret
7/11/13 Woody
7/12/13 quasi
7/12/13 Woody
7/12/13 quasi