Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.