Minimum enclosing rectangle of a convex polygon proof - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T02:11:53Z http://mathoverflow.net/feeds/question/23849 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23849/minimum-enclosing-rectangle-of-a-convex-polygon-proof Minimum enclosing rectangle of a convex polygon proof huhawa 2010-05-07T11:57:10Z 2010-05-07T13:53:29Z <p>Hi,</p> <p>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.</p> <p>Can someone explain why is this true?</p> <p>Thanks in advance</p> http://mathoverflow.net/questions/23849/minimum-enclosing-rectangle-of-a-convex-polygon-proof/23854#23854 Answer by Chad Groft for Minimum enclosing rectangle of a convex polygon proof Chad Groft 2010-05-07T13:53:29Z 2010-05-07T13:53:29Z <p>Suppose you've got your polygon <em>P</em>, embedded in the Euclidean plane with some standard coordinate system. Then there's some rectangle <em>R</em> with horizontal and vertical sides which encloses <em>P</em> 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 <em>&theta;</em> will; so the rectangle <em>R</em><sub><em>&theta;</em></sub> and its area <em>A</em><sub><em>&theta;</em></sub> are really functions of <em>&theta;</em> (and (<em>&pi;</em>/2)-periodic functions at that). As such, <em>A</em> definitely has a minimum at some angle <em>&theta;</em><sub>min</sub>.</p> <p>The meat of the theorem is that, for any angle <em>&phi;</em> where <em>R</em><sub><em>&phi;</em></sub> does not meet the conclusion, the function <em>A</em> does not even have a local minimum. To see this, note that <em>R</em><sub><em>&phi;</em></sub> intersects <em>P</em> at a finite set of points <em>S</em> — usually |<em>S</em>| = 4, but 3 or 2 are also possible. Now consider the rectangle <em>R'</em><sub><em>&theta;</em></sub> which is the smallest rectangle with sides parallel to the <em>&theta;</em>-axes and which contains <em>S</em>, and let <em>A'</em><sub><em>&theta;</em></sub> be its area. Note two things:</p> <ul> <li>For <em>&theta;</em> near <em>&phi;</em>, <em>R'</em><sub><em>&theta;</em></sub> = <em>R</em><sub><em>&theta;</em></sub>, and hence <em>A'</em><sub><em>&theta;</em></sub> = <em>A</em><sub><em>&theta;</em></sub>.</li> <li>Near <em>&phi;</em>, the function <em>A'</em> is <em>concave downward</em>. Why? Divide the rectangle <em>R'<sub>&theta;</sub></em> along the lines between the points of <em>S</em>. We get a convex polygon determined by <em>S</em> (and hence constant), plus |<em>S</em>|-many right triangles. Each triangle has a hypotenuse which stays constant as <em>&theta;</em> changes, and an interior angle which changes as <em>&theta;</em>/2, hence an area which is concave downward.</li> </ul> <p>Under our assumption, <em>&phi;</em> can't possibly be a local minimum of <em>A</em>, let alone a global one; so wherever the global minimum is, it must have a side coincident with one of the sides of <em>P</em>.</p>