Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
There's no need for quotes around the title. –  joriki Oct 21 '12 at 19:24
    
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. –  thischarmingman Oct 21 '12 at 19:28
    
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.) –  joriki Oct 21 '12 at 19:29
    
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. –  Ben Oct 22 '12 at 1:32

1 Answer 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.

share|improve this answer
    
I see, so the key is to have \phi_1 = -\phi_2 and then the area of the rectangle will be the largest one. –  thischarmingman Oct 21 '12 at 19:53
    
@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. –  joriki Oct 21 '12 at 20:40
    
Also, in many cases the points on the rectangle will be degenerate. Triangles are pinned at a vertex of the rectangle, etc. –  Michael Biro Oct 21 '12 at 20:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.