The minimum perimeter enclosing rectangle for a convex polygon
This problem parallels that of the minimum area enclosing rectangle closely. The goal is to find the smallest-box (in terms of perimeters) enclosing a polygon P.
It is interesting to note that very often the two rectangles minimizing the perimeter and the area happen to coincide. One can ask if this is always the case. The following example gives the answer: a polygon is shown (in grey) with its minimum-area enclosing rectangle (to the left) and the minimum perimeter enclosing rectangle (right).
Now, given a direction, the extreme points for P can be computed, in order to determine an enclosing rectangle. But, as in the area problem, it is not necessary to check each single orientation in order to obtain the rectangle with minimum perimeter, thanks to the following result:
The minimum perimeter rectangle enclosing a convex polygon P has a side collinear with an edge of the polygon.
This result restricts the range of possible rectangles to consider to those coinciding with one of the polygon's edges.
Illustrating the above result: the four lines of support (red), with one coinciding with an edge, determine the enclosing rectangle (blue).
Because of the similarities with its area counterpart, this problem can be solved with a similar algorithm based on the Rotating Calipers.
The input for the following algorithm is assumed to be a convex polygon with n vertices given in clockwise order.
- 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 perimeter of the rectangle determined by the four lines, and keep as minimum. Otherwise, consider the current minimum perimeter to be infinite.
- Rotate the lines clockwise until one of them coincides with an edge of its polygon.
- Compute the perimeter of the new rectangle, and compare it to the current minimum perimeter. 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 perimeter enclosing rectangle.
Because two pairs of "calipers" determine an enclosing rectangle, this algorithm considers all possible rectangles that could have the minimum perimeter. 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.
The set of problems deal with triangulations. Two specific ones, the onion triangulation and the spiral triangulation are studied.
December 17th, 1998