Theorem 1.1 shows that we can compute the
diameter of a
given only its strictly convex points.
For convenience and efficiency, then, we will represent a
P with the list
(p1, p2,..., pn)
of its strictly convex points.
The points in the list are given in the order
that we would encounter them if we traversed the boundary
of P in either a clockwise or counterclockwise direction.
As such, the list is actually a circular list
because p1, the first point in the list,
follows pn in a traversal
of the boundary.
For example we represent the
convex polygon in Figure 2
with the list
(p1, p2,..., p9).
(p1, p2,..., p9).
Any algorithm that computes the diameter
of a convex polygon defined by n such points
uses at least n operations.
To see why, consider n - 1 points
lying on the boundary of a circle
and one other point p1 lying slightly outside
the circle such that it is collinear
with the center of the circle and
one other point p2 (see Figure 3).
If p1 is close enough to the boundary then
all n points lie on the convex hull
of the set of points
and the diameter of the hull
is achieved only by the pair p1 and p2.
Finding the diameter of this
involves determining which point lies
outside the circle.
To do this, we must calculate the distance
of each point from the center of the circle.
Thus, we need to perform at least n operations.
Illustration of Lower Bound Argument
There are correct algorithms
that use some constant multiple of n operations.
We consider this optimal because we are essentially using only n operations.
In what follows, we present
three published, optimal algorithms,
only one of which correctly finds the diameter of any
See if you can determine which of the three
After presenting the algorithms we will
present examples of convex polygons for which the incorrect algorithms fail
and then discuss discuss the reasons why they fail.