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 ]
 quasi Posts: 12,067 Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 12, 2013 4:52 AM

ols6000 wrote:
>quasi wrote:
>>
>> I'll try to explain in more detail ...
>>

>Let me say first that I really appreciate the time you've taken
>to help me with this problem. But I am a little dense when it
>comes to proofs, so please bear with me.

No problem.

>> (8) Since L0 does not pass through any of the remaining N-1
>> points, a sufficiently small clockwise rotation of the line
>> L0 through the point (x_k,y_k) will still yield a lower
>> bounding line. Similarly, a sufficiently small
>> counterclockwise rotation of the line L0 through the point
>> (x_k,y_k) will also still yield a lower bounding line.

>
>This I don't understand. Imagine three points forming an
>isosceles triangle,
>
> A---B
> \ /
> C
>
>and a line L0 passing through C, but not either A or B
>(for example, parallel to AB). Rotation of this line doesn't
>change the sum of the distances from L0 to A and L0 to B,

Right.

>therefore rotation doesn't produce a lower bounding line.

You may be confused about my terminology.

By the terminology "lower bounding line", I mean a line such that
all of the N points are above or on the line. Equivalently, a
lower bounding line is a line which lies entirely below the
interior of the convex hull.

Thus the "lower bounding" property is just a geometric property.
In particular, a lower bounding line need not have least possible
distance sum.

If a lower bounding line _does_ have least possible distance sum,
I call such a line an _optimal_ lower bounding line.

The proof I posted starts with an initial line L0, assumed to be
an optimal lower bounding line, that is, L0 is chosen to be
a lower bounding line with least possible distance sum.

Necessarily the line L0 passes through one of the N points (if
not, L0 could be shifted up, reducing the distance sum).

Relative to your example, assume triangle ABC is isosceles with
horizontal base AB, and with vertex C equidistant from vertices
A,B and below side AB. Further assume the line L0 is a horizontal
line through C (thus L0 is parallel to AB) and assume that L0 has
the least possible distance sum of all lower bounding lines
(lines lying entirely below the interior of triangle ABC).

If we rotate L0 slightly counterclockwise through C to yield a
new line L1, the line L1 is still a lower bounding line (the
line L1 is still below the interior of triangle ABC), and as
you point out, the rotation doesn't change the distance sum.

Thus, for this case, we can keep rotating the line L1 through C
until L1 hits the point B. At that instant, L1 is the line CB.

Since, by assumption, L0 has least distance sum and since L1
has the same distance sum as L0, the line L1 is also a lower
bounding line with least possible distance sum, but unlike L0,
L1 passes through at least two of the given points.

Thus, the line L1 validates my claim, for the case of triangle
ABC as specified above.

I didn't claim that _every_ optimal lower bounding line passes
through at least two of the N points. I only claimed that there
_exists_ a lower bounding line passing through at least two of
the N points.

>If the triangle in this example is not isosceles, rotation in
>one direction will increase the sum and the other will decrease
>it.

In that case, choose the rotational direction that decreases
the distance sum. But L0 was assumed to have the _least_
possible distance sum. That means such a rotation is impossible,
subject to the lower bounding condition. But if all lines L1
obtained by a rotation, no matter slight, of the line L0 through
the point C in the given rotational direction fail the lower
bounding condition, it follows that L0 already passes through
at least two of the points A,B,C (that is, L0 passes through
C as well as one of the points A,B).

Thus, in this case, no need to rotate -- the line L0 already
passes through at least two of the given points.

>to be for the general case.

Yes, you previously mentioned that for your data, the y-values
are increasing, but as far as my proof goes, that doesn't matter.

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