Shamos Algorithm[5]
This third algorithm is quite different from
the previous two.
We apply the algorithm to the convex polygon
P = (p_{1}, p_{2},..., p_{n}).
 Antipodal Pairs
 Find all antipodal pairs of points.
An antipodal pair of points consists of two points
such that there exist two parallel lines,
one through each point,
and every other point in the polygon
lies between these two lines.
In Figure 4, p_{5} and p_{9} are an antipodal pair.
Figure 4:
Antipodal Pair

We can picture finding these pairs by rolling
the polygon along the ground.
The point touching the ground and the point furthest from the
ground form such a pair.
We record all such pairs.
We stop rolling the polygon when the first point to touch the
ground returns to the ground.
 Diameter
 The antipodal pair that is at maximum distance apart
achieves the diameter.
For a more formal description of the algorithm see [5,4,9].
The applet below gives an animation of the
Shamos algorithm.Can you construct a counterexample?
Click to run the Shamos algorithm.
This algorithm finishes after a constant multiple of n steps
because, as we roll the polygon, each of the n points
hits the ground exactly once and
becomes the furthest from the ground exactly once.
Therefore, we have at most 2n steps.
Determining the pair at maximum distance from one another
is at most another 2n steps.
For a more formal proof of optimality see [5].
Matthew Suderman
Cmpt 308507