2
$\begingroup$

first of all, sorry for my bad english.

I'm trying to solve this problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=760

I already found the minimum area enclosing rectangle with the help of this information: http://cgm.cs.mcgill.ca/~orm/maer.html

It uses this statement to make the algorithm: The minimum area rectangle enclosing a convex polygon P has a side collinear with an edge of the polygon.

Now, I have to find the "maximum area" enclosing rectangle that fit tightly to the polygon, but I have no idea what kind of property to apply to do so.

Thank you for the attention.

  • 0
    When 2 angles are both less than 45 degrees, I think the maximum area is a square with the longest side of the triangle as the diagonal.2012-10-22

1 Answers 1

1

In general position, there will be one vertex on each edge of the rectangle. If you turn the rectangle, its dimensions will be determined by the two pairs of vertices on opposite edges, and the area will be given by their product as

$ d_1d_2\sin(\phi_1+\delta)\sin(\phi_2+\delta)\;, $

where the $d_i$ are the distances between opposite vertices, the $\phi_i$ are the angles that the lines joining them make with the edges and $\delta$ is the angle of rotation. For this to be stationary with respect to $\delta$, you must have $\phi_1=-\phi_2$, that is, the lines joining opposite vertices must intersect the edges at opposite angles such that turning towards one of them turns away from the other with equal opposite effect on the area.

  • 0
    Also, in many cases the points on the rectangle will be degenerate. Triangles are pinned at a vertex of the rectangle, etc.2012-10-21