A brute-force algorithm
for calculating the diameter of a set of n points
is to simply calculate the distance between each pair of points
and then take the maximum of these n(n - 1) distances.
However, this is inefficient because
we need not consider all pairs of points.
To see why, consider finding the diameter of the set of points
illustrated in Figure 1(a).
Intuitively, we know that point u is not a diameter point
because it is somehow ``inside'' the set.
Likewise, we might even rule out point v
because it is ``between'' two other points.
Point w, on the other hand, might possibly
achieve the diameter with some other point
because it is the leftmost point in the set.
Although intuitions are often difficult to formalize mathematically,
in this case we can formalize them using a structure called the
The convex hull of a set of points is a polygon that has
the shape of an elastic band streched around all the points.
More formally, the convex hull is
the smallest convex polygon
containing all points in the set.
Figure 1(b) shows the convex hull
of the points in Figure 1(a).
Notice that u lies inside the hull and
v lies on the boundary of the hull but not at a ``corner'' like w.
Points like w are said to be strictly convex.
The following theorem confirms our intuition that
only strictly convex points can achieve the diameter
so we can ignore all other points in the set.
This theorem suggests that we can decompose the diameter
problem into two subproblems:
Neither of these problems is trivial.
In fact, many published algorithms that
were thought to compute the answers to both these problems
in minimum time have turned out to be incorrect.
Optimal and correct algorithms have since been discovered
for both these problems.
For solutions to the convex hull problem see e.g. .
- Computing the convex hull of a set of points and
- Computing the diameter of a convex polygon (In this case
the polygon happens to be the convex hull of a set of points.
Recall that a convex hull is a convex polygon).