The maximum distance between two convex polygons
Given two convex polygons P and Q, the goal is to find the
pair(s) of points (p,q) (p belonging to P and
q to Q) maximizing the distance between them.
Intuitively, these points will not belong to the interior of their respective
polygons. The situation is in fact similar to the diameter problem:
The maximum distance between two convex polygons P and Q is
determined by anti-podal pair between the polygons.
Although the terminology is the same, this definition is different from that
of anti-podal pair for a given convex polygon.
The essential difference with an anti-podal pair between
convex polygons is that the lines of support are directed and have opposite
direction. An example is illustrated below:
Not only does the above result imply that only pairs of vertices should be
checked, only specific pairs need to be considered. The fact that they admit
parallel lines of support calls for an algorithm based on the Rotating
Calipers paradigm.
Consider the following algorithm, where the input is assumed to be two convex
polygons P and Q with m and n vertices respectively given in clockwise order.
- Compute the vertex with minimum y coordinate for P (call it
yminP) and the
vertex with maximum y coordinate for Q (call it ymaxQ).
- Construct two lines of support LP and LQ for the polygons
at yminP and
ymaxQ such that the polygons lie to the right of their respective lines
of support. Then LP and LQ have opposite direction, and
yminP and ymaxQ form an anti-podal pair between the polygons.
- Compute dist(yminP,ymaxQ) and keep it as the maximum.
- Rotate the lines clockwise until one of them coincides with an edge of its polygon.
- A new anti-podal pair is determined. The new distance is computed,
compared to the current maximum, which is updated if necessary.
If both lines of support coincide with edges, then a total of three anti-podal
pairs (combinations of the previous vertices and the new vertices) need to be
considered.
- Repeat steps 4 and 5, until the new pair considered is
(yminP,ymaxQ).
- Output the maximum distance.
The Rotating Calipers paradigm ensures all possible anti-podal pairs are
considered. Furthermore, the whole algorithm has linear time complexity, since
(besides the initialization), there are only as many steps as there are
vertices.
A similar algorithm can be used for the minimum distance
between two convex polygons.
December 17th, 1998