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 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 N-1
points, the claim of step (3) holds.

(7) Thus, suppose instead that L0 does not pass through any of
the remaining N-1 points.

(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.

(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
non-vertical 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
N-1 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

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