Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
quasi

Posts: 10,226
Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 8, 2013 7:43 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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 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
Read How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
Scott Berg
7/7/13
Read Re: How to find a bounding line?
Peter Percival
7/7/13
Read Re: How to find a bounding line?
Woody
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Woody
7/8/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/8/13
Read Re: How to find a bounding line?
LudovicoVan
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
Leon Aigret
7/8/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Leon Aigret
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
RGVickson@shaw.ca
7/10/13
Read Re: How to find a bounding line?
Woody
7/10/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/7/13
Read Re: How to find a bounding line?
quasi
7/8/13
Read Re: How to find a bounding line?
William Elliot
7/8/13
Read Re: How to find a bounding line?
Peter Percival
7/8/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
LudovicoVan
7/11/13
Read Re: How to find a bounding line?
quasi
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/11/13
Read Re: How to find a bounding line?
Leon Aigret
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
Leon Aigret
7/11/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi
7/12/13
Read Re: How to find a bounding line?
Woody
7/12/13
Read Re: How to find a bounding line?
quasi

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.