Search All of the Math Forum:

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

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

 Messages: [ Previous | Next ]
 LudovicoVan Posts: 4,025 From: London Registered: 2/8/08
Re: How to find a bounding line?
Posted: Jul 8, 2013 7:50 AM

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

>>

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