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