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 ]
 LudovicoVan Posts: 4,165 From: London Registered: 2/8/08
Re: How to find a bounding line?
Posted: Jul 8, 2013 9:15 AM

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

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