Main homepageRotating Calipers homepageNext problemApplet homepage


The diameter of a convex polygon

The diameter of a polygon is defined as the maximum distance between any two points of the polygon. It is possible for more than one pair of points to determine the diameter. In fact, if the polygon has n vertices, as many as n "diameter pairs" may exist.

Diameter of a convex polygon

A simple example of a polygon's diameter is illustrated to the left. The diameter pair, shown as black dots admits parallel lines of support (shown in red). The diameter is highlighted in light blue.


Obviously, the pair of points determining the diameter of a convex polygon P does not belong to the interior of P. The search should concentrate on the boundary. In fact, only anti-podal pairs of points should be checked, for the diameter is the greatest distance between parallel lines of support. Shamos (1978) provides a simple algorithm computing the anti-podal pairs of a convex n-gon in O(n) time. The diameter can then obtained by going through the list, and outputting the pair with maximum distance. The following is the pseudo-code for Shamos' algorithm, as presented in the text by Preparata and Shamos (1985).
The input is a polygon P={p1,...,pn}.

begin
     p0:=pn;
     q:=NEXT[p];
     while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q)) do
          q:=NEXT[q];
          q0:=q;
          while (q != p0) do
               begin
                    p:=NEXT[p];
                    Print(p,q);
                    while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q) do
                         begin
                              q:=NEXT[q];
                              if ((p,q) != (q0,p0)) then Print(p,q)
                              else return
                         end;
                    if (Area(p,NEXT[p],NEXT[q]) = Area(p,NEXT[p],q)) then
                      if ((p,q) != (q0,p0)) then Print(p,NEXT[q])
                      else Print(NEXT[p],q)
               end
end.

Note that Print(p,q) signifies the output of (p,q) as an anti-podal pair and Area(p,q,r) signifies the signed-area of triangle pqr.
Although this procedure is not as intuitive as the usual Rotating Calipers algorithm, it is essentially the same, and avoids any angle computations.

A more intuitive algorithm would be:
  1. Compute the polygon's extreme points in the y direction. Call them ymin and ymax.
  2. Construct two horizontal lines of support through ymin and ymax. Since this is already an anti-podal pair, compute the distance, and keep as maximum.
  3. Rotate the lines until one is flush with an edge of the polygon.
  4. A new anti-podal pair is determined. Compute the new distance, compare to old maximum, and update if necessary.
  5. Repeat steps 3 and 4 until the anti-podal pair considered is (ymin,ymax) again.
  6. Output the pair(s) determining the maximum as the diameter pair(s).
Still, the above procedure (given in pseudocode) happens to be very useful, as other information can be obtained from the anti-podal pairs, like the width of a convex polygon.

Main homepageRotating Calipers homepageNext problemApplet homepage
December 17th, 1998