quasi
Posts:
11,481
Registered:
7/15/05


Re: How to find a bounding line?
Posted:
Jul 12, 2013 2:11 AM


ols6000 wrote: >quasi wrote: >> >> But do you now at least acknowledge my previous claim that >> there is an optimal bounding line which passes through two >> consecutive points of the convex hull? > >Your claim seems reasonable (I certainly took note of it), but >I still don't understand your proof.
I'll try to explain in more detail ...
(1) The goal is to show the following claim: Of all lower bounding lines (that is, lines satisfying the nonnegativity condition) with least possible distance sum, there is one which passes through two consecutive points of the convex hull.
(2) Any lower bounding line which passes through two of the N points also passes through an edge of the convex hull and hence passes through two consecutive points of the convex hull.
(3) Thus it suffices to establish the following claim: Of all lower bounding lines with least possible distance sum, there is one which passes through at least two of the N points.
(4) Assume line L0 is a lower bounding line with least possible distance sum, s0 say.
(5) By minimality of s0, L0 must pass through at least one of the N points, say (x_k,y_k).
(6) If L0 also passes through at least one of the remaining N1 points, the claim of step (3) holds.
(7) Thus, suppose instead that L0 does not pass through any of the remaining N1 points.
(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.
(9) Let a0 be the slope of L0. As a consequence of step (8), any line L with slope a through the point (x_k,y_k) will be a lower bounding line if a is sufficiently close to a0.
(10) For a line L with slope a through the point (x_k,y_k), the distance sum s depends only on a (all other values are held constant). Moreover, s is a polynomial in a of degree at most 1.
(11) This leads to two cases. Either s is degree 1 in a, or s is constant as a function of a.
(12) Assume first that s is degree 1 in a.
(13) Since s is a degree 1 polynomial in terms of a, s is either increasing or decreasing as a function of a.
(14) If s is an increasing function of a, then a small negative change (a small decrease) in the value of a will decrease the value of s, and similarly, if s is a decreasing function of a, then a small positive change (a small increase) in the value of a will decrease the value of s.
(15) Based on steps (9) and (14), it follows that there is a lower bounding line L1 through (x_k,y_k) with distance sum s1 < s0, contrary to our choice of L0 as a lower bounding line with least possible distance sum.
(16) Thus, the assumption of step (12) fails.
(17) It follows that s is constant as a function of a.
(18) But then, since s is constant as a function of a, any nonvertical line L through the point (x_k,y_k) will have distance sum _equal_ to s0, so we can rotate the lower bounding line L0 through the point (x_k,y_k), either clockwise or counterclockwise (one or the other will work, possibly both) to get an optimal lower bounding line L1 through the point (x_k,y_k) such that L1 also passes through at least one of the remaining N1 points.
(19) Hence we've established the claim of step (3), which, as previously noted, implies the claim of step (1), thus achieving our goal.
If there are steps in the above proof which are not convincing, please let me know the first such step, and I'll try to clarify further.
quasi

