Diameter of a Convex Polygon

Theorem 1.1 shows that we can compute the diameter of a convex polygon given only its strictly convex points. For convenience and efficiency, then, we will represent a convex polygon P with the list (p₁, p₂,..., p_n) 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 p₁, the first point in the list, follows p_n in a traversal of the boundary. For example we represent the convex polygon in Figure 2 with the list (p₁, p₂,..., p₉).

Figure 2: Convex polygon (p₁, p₂,..., p₉).

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 p₁ lying slightly outside the circle such that it is collinear with the center of the circle and one other point p₂ (see Figure 3).

Figure 3: Illustration of Lower Bound Argument

If p₁ 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 p₁ and p₂. Finding the diameter of this polygon 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.

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 convex polygon. See if you can determine which of the three is correct. 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.