4
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

Just a historical footnote. The first proof appeared in a paper by Freeman & Shapira:

Freeman, Herbert, and Ruth Shapira. "Determining the minimum-area encasing rectangle for an arbitrary closed curve." Communications of the ACM 18.7 (1975): 409-413. (ACM link.)

They partition the proof into one theorem that carries most of the water, and then a second theorem that follows easily from the first:

THEOREM 1. Given a rectangle with four points arbitarily chosen such that no edge contains more than one point, there exists another rectangle such that each edge contains one and only one of these points and the area of the rectangle is less than that of the given rectangle.

THEOREM 2. The rectangle of minimum area enclosing a convex polygon has a side collinear with one of the edges of the polygon.

         

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .