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/