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 ]
 quasi Posts: 12,046 Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 10, 2013 5:13 PM

ols6000 wrote:
>
>This has not been proved.

I think it has.

>Only the fact that a "best" bounding line must pass through at
>least one point has been shown (by quasi).
>
>If it turns out to be true that said line must pass through at
>least two points, then we have an O(n^2) method, which is too
>slow for practical use.
>
>The convex hull may be found in O(n) time, given that the data
>is already sorted, but even if the optimum line(s) pass through
> two points on the hull (and this hasn't yet been proved),

I claim it _has_ been proved.

>the method is still O(n^2).
>
>The hypothesis that an optimum line must pass through two
>neighboring points of the original data is incorrect, as shown
>by counter-example.
>
>It may be that an optimum line must pass through two
>neighboring points of the convex hull, but this has not been
>proved.

It's a triviality (draw a picture).

If a bounding line passes through two points of the convex hull
it must pass through two _consecutive_ points of the convex hull.

quasi

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