Maximum Rectangle within a Quadrilateral
Date: 10/25/2001 at 12:33:26 From: Christophe Floutier Subject: Maximum area rectangle into a quadrilateral Hello, I have a problem: I need to extract from a quadrilateral the maximum area rectangle inside it. I've tried many algorithms of my own without any success. I wonder if it is possible. Thanks, Christophe Floutier.
Date: 10/25/2001 at 16:03:57 From: Doctor Rob Subject: Re: Maximum area rectangle into a quadrilateral Thanks for writing to Ask Dr. Math, Christophe. Fact A: If a rectangle has two adjacent vertices lying in the interior of the quadrilateral, you can increase its area by moving the side connecting them away from the opposite side until one or both of its ends is touching the boundary. Fact B: If a rectangle has two diagonally opposite vertices lying in the interior of the quadrilateral, and the other two lying on the boundary, you can rotate the rectangle just a little about one of the boundary vertices so that the previous case holds, without changing the area. These two facts imply that the rectangle with largest area must have at least three vertices on the boundary. Now given that, there are several cases, depending on whether the vertices of the rectangle of largest area lie at vertices of the quadrilateral (where the interior angle is obtuse), on edges but not at vertices, or not on the boundary at all. In each case, you can set up the problem using analytic geometry and find the maximum area using calculus. When you have found the maximum for each case, just pick the case for which that value is largest, and you have your answer. The multiplicity of cases is confusing, and you have to be careful setting up the area function in each case, but this can be carried out. If you need more detail, or have a particular quadrilateral, write back and I'll try to help further. Sorry that this is so complicated, but that's the best way I know to achieve what you want. This is similar to the same problem for triangles: one of the rectangle's sides must lie along one of the triangle's sides, so there are three cases. The maximum area for each case can be found, and then the largest of these tells you which case and what the best rectangle is. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.