The original statement follows from the more general statement because if v is the first local maximum for u along the path u...w...v then as we traverse the path from u to v our distance from u increases monotonically. From the more general statement, then, we know that our distance from w also increases monotonically as we traverse from w to v.
We present the proof as two lemmas. These lemmas will also be useful for proving counterexamples to the Dobkin and Snyder algorithm later on.
The first lemma shows that d (w, x) d (w, v) provided that line segments wv and ux intersect.
PROOF See Figure 16 for an example and an illustration of the proof.
Let luv, lux and lxv denote the lines determined by u and v, u and x and x and v, respectively. Let t be the intersection of lxv and the line through u perpendicular to lxv. By the Pythagorean theorem, d (x, t) d (v, t):d (x, t)2 = d (u, x)2 - d (u, t)2Thus, x and t must lie on the same side of v.
d (v, t)2 = d (u, v)2 - d (u, t)2
so since d (u, x) d (u, v) we have d (x, t) d (v, t).
Let t' be the intersection of lxv and the line through w perpendicular to lxv. Since segment wv intersects segment ux and x and t are on the same side of v, then at least one of x or t lies between t' and v. Thus, d (x, t') d (v, t'). By the Pythagorean theorem, then, d (w, x) d (w, v):d (w, x)2 = d (x, t')2 + d (t', w)2
d (w, v)2 = d (v, t')2 + d (t', w)2
so since d (x, t') d (v, t') we have d (w, x) d (w, v).
This next lemma shows that in any convex polygon line segments ux and wv do intersect.
PROOF The situation is illustrated in Figure 17.
Because the polygon is convex, line segments ux and wv lie entirely inside the polygon. Thus, by the Jordan Curve Theorem, segment wv is the border between two disjoint subsets of the polygon: one set contains u and the other x. Consequently, if segment ux does not intersect wv then it must include some point outside the polygon in order to join u and x. This is a contradiction because ux lies entirely inside the polygon. Therefore, ux intersects wv.