quasi
Posts:
10,970
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 N1 >> 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, > > AB > \ / > 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 yvalues are increasing, but as far as my proof goes, that doesn't matter.
quasi

