The width of a convex polygon
The width of a convex polygon is defined as the minimum distance between parallel lines of support. This definition already hints at the characteristics of the width. However, a convex polygon admits parallel lines of support in any direction, and for each direction the width is (usually) different. Fortunately, not every direction needs to be checked.
Consider a line segment [a,b], and two parallel lines through a and b. By rotating the lines about these points, the distance between them either increases or decreases. Specifically, there is always a preferred direction of rotation that the lines can be rotated to decrease the distance between them.
This simple result can be applied to the problem of the width: not all directions need to be considered. Suppose a polygon is given, along with two parallel lines of support. If neither of the lines coincides with an edge, then it is always possible to rotate them to decrease the distance between them. Therefore, two parallel lines of support do not determine the width unless one of them coincides with an edge.
This means that only anti-podal vertex-edge and edge-edge pairs need to be considered in the computation of the width.
A convex polygon's width. The diameter pair, shown as black dots admits parallel lines of support (shown in red). The diameter is highlighted in light blue.
An algorithm similar to that of the diameter problem can be used to go through the anti-podal pairs list of the polygon, determine the vertex-edge and edge-edge pairs, and compute the width from that.
An alternative would be:
- Compute the polygon's extreme points in the y direction. Call them ymin and ymax.
- Construct two horizontal lines of support through ymin and ymax. If one (or both) of the lines coincide with an edge, then a anti-podal vertex-edge or edge-edge pair is already determined. In that case, compute the distance between the lines, and keep as the minimum.
- Rotate the lines until one is flush with an edge of the polygon.
- A new anti-podal vertex-edge pair (or edge-edge pair in case both lines coincide with edges) is determined. Compute the new distance between the lines, compare to old minimum, and update if necessary.
- Repeat steps 3 and 4 until the lines of support (calipers) have reached their original horizontal position.
- Output the pair(s) determining the minimum as the width determining pair(s).
Again, the more intuitive algorithm has the disadvantage of require angle computations. However, sometimes the simpler, more intuitive Rotating Calipers algorithm must be used, as in the computation of the maximum distance between convex polygons.
December 17th, 1998