Minimum enclosing rectangle of a convex polygon proof

2010-05-07T11:57:10Z

Hi,

I've been reading about the rotating calipers algorithm for solving the minimum-area enclosing rectangle problem. It relies on a theorem: The rectangle of minimum area enclosing a convex polygon has a side collinear with one of the edges of the polygon.

Can someone explain why is this true?

Thanks in advance

Answer by Chad Groft for Minimum enclosing rectangle of a convex polygon proof

2010-05-07T13:53:29Z

Suppose you've got your polygon P, embedded in the Euclidean plane with some standard coordinate system. Then there's some rectangle R with horizontal and vertical sides which encloses P and is as small as possible among all such rectangles (just take horizontal lines through the topmost and bottommost points, and vertical lines through the rightmost and leftmost points). Translating the coordinate system doesn't change the rectangle or its area, but rotating it through an angle θ will; so the rectangle R_θ and its area A_θ are really functions of θ (and (π/2)-periodic functions at that). As such, A definitely has a minimum at some angle θ_min.

The meat of the theorem is that, for any angle φ where R_φ does not meet the conclusion, the function A does not even have a local minimum. To see this, note that R_φ intersects P at a finite set of points S — usually |S| = 4, but 3 or 2 are also possible. Now consider the rectangle R'_θ which is the smallest rectangle with sides parallel to the θ-axes and which contains S, and let A'_θ be its area. Note two things:

For θ near φ, R'_θ = R_θ, and hence A'_θ = A_θ.
Near φ, the function A' is concave downward. Why? Divide the rectangle R'_θ along the lines between the points of S. We get a convex polygon determined by S (and hence constant), plus |S|-many right triangles. Each triangle has a hypotenuse which stays constant as θ changes, and an interior angle which changes as θ/2, hence an area which is concave downward.

Under our assumption, φ can't possibly be a local minimum of A, let alone a global one; so wherever the global minimum is, it must have a side coincident with one of the sides of P.

Minimum enclosing rectangle of a convex polygon proof - MathOverflow

Minimum enclosing rectangle of a convex polygon proof

Answer by Chad Groft for Minimum enclosing rectangle of a convex polygon proof