The minimum area enclosing rectangle for a convex polygon
Given a convex polygons P, what is the smallest-box (in terms of surface are) enclosing P? Technically, given a direction, the extreme points for P can be computed and an enclosing rectangle is therefore constructed. But is it necessary to check each single orientation in order to obtain the rectangle with minimum area? The answer, thankfully, is no.
The minimum area rectangle enclosing a convex polygon P has a side collinear with an edge of the polygon.
The above result dramatically restricts the range of possible rectangles. Not only is it not necessary to check all directions, but only as many as the polygon's number of edges.
Illustrating the above result: the four lines of support (red), with one coinciding with an edge, determine the enclosing rectangle (blue).
A simple algorithm would be to compute for each edge the corresponding rectangle collinear with it. But the construction of this rectangle would imply computing the polygon's extreme points for each edge, a process that takes O(n) time (for n edges). The entire algorithm would then have quadratic time complexity.
A much more efficient algorithm can be found. Instead of recomputing the extreme points, it is possible to update them in constant time, using the Rotating Calipers.
Indeed, consider a convex polygon, with a two pair of lines of support through all four usual extreme points in the x and y directions.
The four lines already determine an enclosing rectangle for the polygon. But unless the polygon has a horizontal or vertical edge, this rectangle is not a candidate for the minimum area.
However, the lines can be rotated until the above condition is satisfied. This procedure is at the heart of the following algorithm. The input is assumed to be a convex polygon with n vertices given in clockwise order.
Because two pairs of "calipers" determine an enclosing rectangle, this algorithm considers all possible rectangles that could have the minimum area. Furthermore, aside from the initialization, there are only as many steps in the algorithm's main loop as there are vertices. Thus the algorithm has linear time complexity.
- Compute all four extreme points for the polygon, and call them xminP, xmaxP, yminP ymaxP.
- Construct four lines of support for P through all four points. These determine two sets of "calipers".
- If one (or more) lines coincide with an edge, then compute the area of the rectangle determined by the four lines, and keep as minimum. Otherwise, consider the current minimum area to be infinite.
- Rotate the lines clockwise until one of them coincides with an edge of its polygon.
- Compute the area of the new rectangle, and compare it to the current minimum area. Update the minimum if necessary, keeping track of the rectangle determining the minimum.
- Repeat steps 4 and 5, until the lines have been rotated an angle greater than 90 degrees.
- Output the minimum area enclosing rectangle.
A similar but less known problem is the minimum perimeter enclosing rectangle. It is interesting to note that these two problems are distinct since there exists (although rare) cases of polygons where the minimum area enclosing rectangle does not coincide with the minimum perimeter enclosing rectangle.
December 17th, 1998