##

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 *p*_{3} and *p*_{7}.

First consider the clockwise direction.
If we start at point *p*_{1}, *p*_{2}, *p*_{3} or *p*_{8}
then, by Theorem 3.1(2),
the search for local maxima
does not pass point *p*_{5} until we begin searching
for a local maximum for *p*_{4}.
At this point we have discovered a local maximum
for *p*_{3} and it is not *p*_{7} because
our search has not passed *p*_{5} yet.
When we reach *p*_{4}, then,
the algorithm's state is equivalent to
starting the algorithm at *p*_{4}
because the search for a local maximum
begins at *p*_{5}.
If we start the algorithm at point *p*_{4}, *p*_{5}, *p*_{6} or *p*_{7}
then, by Theorem 3.1(3),
the search for local maxima does
not pass point *p*_{1} until we search
for a local maximum for *p*_{1}.
At this point we have discovered a local maximum
for *p*_{7} but it is not *p*_{3} because
our search hasn't reached *p*_{3} yet.
When we reach *p*_{1}, then,
the algorithm's state is equivalent to
starting the algorithm at *p*_{1}
because the search for a local maximum begins
at *p*_{2}.
Thus, no matter which point we start
with we will never encounter the pair
*p*_{3} and *p*_{7}.

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

*Back to Corollary 3.1a...*

Matthew Suderman

Cmpt 308-507