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

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

Posts: 10,411
Registered: 7/15/05
Re: How to find a bounding line?
Posted: Jul 12, 2013 4:52 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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.

>My data has some additional constraints, but your proof seemed
>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
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.