##

Dobkin and Snyder Algorithm[3]

The second algorithm is very similar to the
Snyder and Tang algorithm.
As before, we apply the algorithm to the convex polygon
*P* = (*p*_{1}, *p*_{2},..., *p*_{n}).
**initialization**
- Let
*A* and *A'* be point *p*_{1} and *B* and *B'* be point *p*_{2}.
At any moment in the loop step,
*A'* and *B'* is the pair that is furthest apart
of any pair encountered up to that moment.

**loop**
- Beginning at
*B*, traverse the points
in order to find the first point *C* whose next neighbor
is closer than *C* to *A*.
We call *C* a **local maximum** for *A*.
If the distance between *A* and *C* is greater
than the distance between *A'* and *B'* then update *A'* and *B'*:
let *A'* be *A* and *B'* be *C*.
Now prepare to repeat this procedure
for *A*'s next neighbor:
advance *A* to this neighbor and let *B* be point *C*.
If *A* = *B* then advance *B* to its next neighbor.
If *A* = *p*_{1} then terminate because *A* has gone once around the polygon;
otherwise, repeat this loop step.

The applet below gives an animation of the
Dobkin and Snyder algorithm.*Can you construct a
counterexample?*

Click to run the Dobkin and Snyder algorithm.

This algorithm terminates after a constant multiple of *n* steps.
In the algorithm,
we have two traversals occuring simultaneously.

The first traversal involves *A*
and traverses the entire polygon exactly one time
(recall that we stop when *A* = *p*_{1}).

The second traversal starts at *B* = *p*_{2}
and searches for a **local maximum** for *A*
each time we advance *A* to its next neighbor.
When it stops temporarily, we assign *C* its current position.
It restarts where it left off at *B* = *C* each time we repeat the loop step.
The second traversal is always ahead but not more than *n* - 1 points
ahead of the first traversal.
It starts at *B* = *p*_{2}, one point ahead of *A* = *p*_{1}
and remains ahead because *A* cannot be its own **local maximum**.
It doesn't, however, get more than *n* - 1 points ahead
because the transition from *n* - 1 points to *n*
points ahead can never occur.
If this were to occur then we
would have compared the distance between
*A* and its previous neighbor to the distance between *A* and itself
and found that *A* was closer to its neighbor
than it was to itself. This is impossible.

So, since the first traversal visits
exactly *n* points and the second traversal
is at most *n* - 1 points ahead,
then the second traversal can visit
at most *n* + *n* - 1 points.
Put together, the algorithm uses a total of 3*n* - 1 steps.

Matthew Suderman

Cmpt 308-507