## Algorithm Counterexample I

One family of convex polygons for which the Snyder and Tang algorithm fails is described in [2]. They are oval-shaped convex polygons with at least two pairs of points. See Figure 5 for an example. One pair lies on the longest diameter of the oval (p3 and p7 in the figure) and the other on the shortest diameter of the oval (p1 and p5 in the figure). Consequently, the pair on the longest diameter achieves the diameter of the polygon. However, if the algorithm starts with a point on the shorter diameter it will be fooled into reporting that pair as the diameter of the polygon. More formally, the pair, pi and pj, on the shorter diameter are placed so that:
• Points pi and pj do not achieve the diameter and
• All other point lie inside the circles centered at pi and pj with radiuses both equal to d (pi, pj).

These polygons are counterexamples for the Snyder and Tang algorithm because:

They can be constructed. (It's no use defining a family counterexamples that are impossible to construct; otherwise they can't be counterexamples!) The simplest such polygon consists of four points (p1p2p3p4) with p2 near one intersection and p4 near the other interesection of the circles centered at p1 and p3 each of radius d (p1, p3). See Figure 6. Thus, p1 and p3 are our pi and pj and p2 and p4 alone achieve the diameter which is slightly less than d (p1, p3).

Because of the way the polygon is constructed, the point furthest from pi is pj, and vice versa. Recall that all points other than pi and pj lie inside the circles centered at pi and pj of radius d (pi, pj). As a result, if the algorithm begins at A = pi then it will find B = pj at a maximum distance from A = pi. Then, when it searches for a point at a maximum distance from B = pj it finds pi so the algorithm incorrectly terminates with A = pi and B = pj as two points achieving the diameter.

See if you can construct one of the polygons described above and then watch how the Snyder and Tang algorithm handles it.

Click to run the Snyder and Tang algorithm.

Matthew Suderman
Cmpt 308-507