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).
Figure 5:
Snyder and Tang Counterexample
|
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
(p1, p2, p3, p4) 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).
Figure 6:
Smallest Counterexample to the Snyder and Tang Algorithm
|
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