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
    There's no need for quotes around the title.2012-10-21
  • 0
    Sorry, I did it because I think that is not a proper term for a what I'm looking for, since obviously there is an infinite number of rectangles larger than the polygon. But I'm looking the largest rectangle that fit tightly to the polygon.2012-10-21
  • 0
    I see -- in that case the version in the body with the quotes only around "maximum area" a) seems to make more sense to me and b) would prevent the misunderstanding that the title has simply been placed in quotes as a whole. (Also I see no reason to introduce a discrepancy between title and body in that respect.)2012-10-21
  • 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
    I see, so the key is to have \phi_1 = -\phi_2 and then the area of the rectangle will be the largest one.2012-10-21
  • 0
    @thischarmingman: No, that's just a necessary condition, just like an edge of the rectangle being colinear with an edge of the polygon is just a necessary condition for the minimum rectangle, not a suffcient one.2012-10-21
  • 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