next up previous


The Correct Part of the Dobkin and Snyder Correctness Proof

We prove that the following statement is true: If v is the first local maximum for u on the boundary path u...w...v of a convex polygon then none of the points other than v along that path can be a local maximum for w. In fact, we actually prove something more general: if u...w...x...v represents the points on a path along the boundary of a convex polygon such that d (u, x) $ \leq$ d (u, v), then d (w, x) $ \leq$ d (w, v).

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) $ \leq$ d (w, v) provided that line segments wv and ux intersect.

Lemma A.2   Let u, v and x be points such that d (u, x) $ \leq$ d (u, v). If w is a point such that line segments wv and ux intersect then d (w, x) $ \leq$ d (w, v).

PROOF See Figure 16 for an example and an illustration of the proof.

Figure 16: Illustration for the proof of Lemma A.2.
\begin{figure}\centering
\htmlrule\\
\par\begin{center}
 \epsfbox{figs/distance.eps}\
\end{center} \htmlrule \end{figure}

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) $ \leq$ d (v, t):
d (x, t)2 = d (u, x)2 - d (u, t)2
d (v, t)2 = d (u, v)2 - d (u, t)2
so since d (u, x) $ \leq$ d (u, v) we have d (x, t) $ \leq$ d (v, t).
Thus, x and t must lie on the same side of v.

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') $ \leq$ d (v, t'). By the Pythagorean theorem, then, d (w, x) $ \leq$ 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') $ \leq$ d (v, t') we have d (w, x) $ \leq$ d (w, v).
$ \Box$

This next lemma shows that in any convex polygon line segments ux and wv do intersect.

Lemma A.3   If u...w...x...v represents the points on a path along the boundary of a convex polygon then line segments ux and wv intersect.

PROOF The situation is illustrated in Figure 17.

Figure 17: Intersections in a Convex Polygon
\begin{figure}\centering
\htmlrule\\
\par\begin{center}
 \epsfbox{figs/intersection.eps}\
\end{center} \htmlrule \end{figure}

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.$ \Box$

Back to Dobkin and Snyder correctness proof outline...


next up previous
Matthew Suderman
Cmpt 308-507