Snyder and Tang Algorithm[6]

We apply the algorithm to the convex polygon P = (p₁, p₂,..., p_n).

initialization

Let A be any point p_i. Traverse the points in order some direction away from A to find a point B furthest from A.

loop

If the distance from B to each point before and after A is less than the distance between A and B then terminate the algorithm because A and B achieve the diameter. Otherwise, traverse the points away from A in the direction of increasing distance from B to find a point C at a maximum distance from B. Let A now be point B, B now be point C and repeat this loop step.

The applet below gives an animation of the Snyder and Tang algorithm. Can you construct a convex polygon for which the algorithm incorrectly calculates the diameter?

Click to run the Snyder and Tang algorithm.

Calculating the number of steps required by this algorithm is not easy. In fact, at first glance, it might even be difficult to see that it always terminates. However, it does terminate because the distance between A and B only increases at each step. This distance cannot increase forever because we know that there are n(n - 1) pairs of points and therefore at most n(n - 1) different distances between A and B. In fact, [6] claims that the algorithm is optimal, i.e. requires at most some constant multiple of n steps, using the following argument:

Since this method goes around the boundary only in the direction of increasing distance, it avoids comparing the same pair of points twice.

Do you agree with this? How many pairs of points are there? Note that we aren't questioning correctness here, just optimality. We will discuss correctness later.