##

Snyder and Tang Algorithm[6]

We apply the algorithm to the convex polygon
*P* = (*p*_{1}, *p*_{2},..., *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.

Matthew Suderman

Cmpt 308-507