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 (p₃ and p₇ in the figure) and the other on the shortest diameter of the oval (p₁ and p₅ 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, p_i and p_j, on the shorter diameter are placed so that:

Points p_i and p_j do not achieve the diameter and
All other point lie inside the circles centered at p_i and p_j with radiuses both equal to d (p_i, p_j).

Figure 5: Snyder and Tang Counterexample

[画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/snyder_tang_counterexample.eps}\ \end{center} \htmlrule \end{figure}]

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 (p₁, p₂, p₃, p₄) with p₂ near one intersection and p₄ near the other interesection of the circles centered at p₁ and p₃ each of radius d (p₁, p₃). See Figure 6. Thus, p₁ and p₃ are our p_i and p_j and p₂ and p₄ alone achieve the diameter which is slightly less than $ \sqrt{3}$d (p₁, p₃).

Figure 6: Smallest Counterexample to the Snyder and Tang Algorithm

[画像:\begin{figure}\centering \htmlrule\\ \par\begin{center} \epsfbox{figs/smallest_counterexample.eps}\ \end{center} \htmlrule \end{figure}]

Because of the way the polygon is constructed, the point furthest from p_i is p_j, and vice versa. Recall that all points other than p_i and p_j lie inside the circles centered at p_i and p_j of radius d (p_i, p_j). As a result, if the algorithm begins at A = p_i then it will find B = p_j at a maximum distance from A = p_i. Then, when it searches for a point at a maximum distance from B = p_j it finds p_i so the algorithm incorrectly terminates with A = p_i and B = p_j 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.

next up previous

Matthew Suderman
Cmpt 308-507