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₁, p₂,..., p_n).

initialization

Let A and A' be point p₁ and B and B' be point p₂. 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₁ 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₁).

The second traversal starts at B = p₂ 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₂, one point ahead of A = p₁ 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 3n - 1 steps.