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 7:50 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

"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. 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...

Julio




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.