## Proof of Corollary 3.1a

Corollary 3.1a states the following: The Dobkin and Snyder algorithm will fail regardless of the point we start with or the direction in which we traverse the polygon.

By Theorem 3.1(4), all we need to prove is that the algorithm never considers the pair p3 and p7.

First consider the clockwise direction. If we start at point p1, p2, p3 or p8 then, by Theorem 3.1(2), the search for local maxima does not pass point p5 until we begin searching for a local maximum for p4. At this point we have discovered a local maximum for p3 and it is not p7 because our search has not passed p5 yet. When we reach p4, then, the algorithm's state is equivalent to starting the algorithm at p4 because the search for a local maximum begins at p5. If we start the algorithm at point p4, p5, p6 or p7 then, by Theorem 3.1(3), the search for local maxima does not pass point p1 until we search for a local maximum for p1. At this point we have discovered a local maximum for p7 but it is not p3 because our search hasn't reached p3 yet. When we reach p1, then, the algorithm's state is equivalent to starting the algorithm at p1 because the search for a local maximum begins at p2. Thus, no matter which point we start with we will never encounter the pair p3 and p7.

Symmetric arguments show that the algorithm will fail in the counterclockwise direction.

Back to Corollary 3.1a...

Matthew Suderman
Cmpt 308-507