The Correct Part of the Dobkin and Snyder Correctness Proof

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.

PROOFSee Figure 16 for an example and an illustration of the proof.

Letl_{uv},l_{ux}andl_{xv}denote the lines determined byuandv,uandxandxandv, respectively. Lettbe the intersection ofl_{xv}and the line throughuperpendicular tol_{xv}. By the Pythagorean theorem,d(x,t)d(v,t):Thus,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 sinced(u,x)d(u,v) we haved(x,t)d(v,t).xandtmust lie on the same side ofv.

Lett'be the intersection ofl_{xv}and the line throughwperpendicular tol_{xv}. Since segmentwvintersects segmentuxandxandtare on the same side ofv, then at least one ofxortlies betweent'andv. 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 sinced(x,t')d(v,t') we haved(w,x)d(w,v).

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

PROOFThe situation is illustrated in Figure 17.

Because the polygon is convex, line segmentsuxandwvlie entirely inside the polygon. Thus, by theJordan Curve Theorem, segmentwvis the border between two disjoint subsets of the polygon: one set containsuand the otherx. Consequently, if segmentuxdoes not intersectwvthen it must include some point outside the polygon in order to joinuandx. This is a contradiction becauseuxlies entirely inside the polygon. Therefore,uxintersectswv.

Matthew Suderman

Cmpt 308-507