Diameter Algorithm Based on Convex Hull

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).

Figure: Set of points(a) and its Convex Hull(b).

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

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 convex hull. 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.

Theorem 1.1 Let x and y be two points in a set of points S. If the distance between x and y is equal to the diameter of S then x and y are strictly convex points. (Click for the proof.)

This theorem suggests that we can decompose the diameter problem into two subproblems:

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).

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. [7].

next up previous

Matthew Suderman
Cmpt 308-507