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 ]
LudovicoVan

Posts: 3,201
From: London
Registered: 2/8/08
Re: How to find a bounding line?
Posted: Jul 8, 2013 9:15 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"Julio Di Egidio" <julio@diegidio.name> wrote in message
news:kre8of$1hd$1@dont-email.me...
> "quasi" <quasi@null.set> wrote in message
> news:vqukt8huprh8hvhi21tmb47a29m41558kf@4ax.com...

>> ols6000 wrote:
>>>quasi wrote:
>>>>
>>>> Firstly, it's clear that if y = ax + b is an optimal bounding
>>>> line, then it must pass through one of the N points, otherwise
>>>> b can be increased [edit], contrary to minimality of the sum.

>>>
>>>I agree.
>>>

>>>> But in fact, I'll show that there is an optimal line which
>>>> passes through at least two of the N points, not just one.

>>>
>>>It seems likely, but I don't follow your proof.

>>
>> I looked at it again. I think my proof that there is an optimal
>> lower bounding line through at least two points is good.
>>
>> Based on that result, O(N^2) is automatic.

>
> The problem is that any of those lines is a candidate solution, isn't it?
> The convex hull in this problem can be found in O(N) (points are sorted by
> their first coordinate, we just need a scan of all points). If M is the
> number of points of the convex hull, where M=N in the worst case, there
> are M-1 candidates to check, N-1 in the worst case. Moreover, for each
> candidate, we need re-compute the cost function (right?), which amounts to
> a scan of at least N-2 points.


In fact, no: at the first scan we can already reduce the cost function to a
function of a and b only, so re-computing the cost function is just a matter
of plugging in values for a and b. The complexity would be O(N+N).

Could better be done? E.g. do we really need to check all candidates?

Julio

> We end up with something like O(N+N^2). Is that what you had in mind?
>
> That said, there is a lot of geometric structure in that set of points,
> yet, if there is any way not to do all that work, I am not seeing it...





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.