Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

In this post we are looking for algorithms / ideas on how to find the maximum-area-rectangle inside a convex polygon.

In the following figure, numbers are the areas of the fitted rectangles. As shown a desired rectangle can vary in each dimension and can be in any angle.

Edit:

We don't have any clear idea how to deal with the problem mentioned as so we asked here. Nevertheless, we guess the maximum-area-rectangle may be one of those that has one edge aligned on (not necessarily the same length edge, of course) an edge of the polygon.

enter image description here

share|improve this question
1  
Could you specify what software you are using? Also, post your work this far, or the general approach you have worked out to solve this. Maybe someone can improve what you have done already. In my experience that'll result in far more useful answers than just posting a question "out of the blue". –  Martin Apr 26 '13 at 13:40
1  
Closely related: gis.stackexchange.com/questions/22895/…. –  whuber Apr 26 '13 at 13:43
    
@Martin Software: Programming in Python then will be in Fortran if required. We have a guess that based on our previous post here also mentioned above by whuber that may be a rectangle with an edge in common with polygon would be an answer. –  Developer Apr 26 '13 at 13:48
1  
Your problem is a really interesting one, and I think I managed to find a solving algorithm here and here. –  nickves Apr 27 '13 at 15:41
1  
@nickves Thanks for the links. Would you please put these info as answer with a little explanation of the algorithms? It will be potentially a good answer to be accepted. –  Developer Apr 28 '13 at 1:35

3 Answers 3

Some notes too big to put into a comment (though this doesn't suggest an obvious algorithm):

The punch line (EDITED): At least two vertices of the maximum area rectangle must lie on the boundary of the polygon (i.e. along an edge, or at a vertex). And if the maximum area rectangle is not a square, then at least three vertices must lie on the boundary of the polygon.

I proved it to myself in four steps:

Note #1: At least one vertex of the maximum area rectangle will always lie on the boundary of the polygon. This is pretty obvious, but a proof could go like this (by contradiction): Suppose you had a "maximal" rectangle with no vertex on the boundary of the polygon. That means there would be at least a little room around each of its vertices. So you could expand your rectangle a bit, contradicting its maximality.

Note #2: At least two vertices of the maximum area rectangle will always lie on the boundary of the polygon. A proof could go like this (again by contradiction): Suppose you had a "maximal" rectangle with only one vertex on the boundary (guaranteed by Note #1). Consider the two edges not adjacent to that vertex. Since their endpoints are NOT on the boundary, there's a little room around each. So either of those edges could be "extruded" a bit, expanding the polygon's area and contradicting its maximality.

Note #3: There are two diagonally opposite vertices of the maximum area rectangle that lie on the boundary of the polygon. (We know from Note #2 that there are at least two, but not necessarily that they're across from each other.) But again by contradiction, if the only two boundary vertices were adjacent, then the opposite edge (neither of whose vertices are on the boundary) could be extruded a little bit, increasing the area of the rectangle and contradicting its maximality.

Note #4: (EDITED) If the maximum area rectangle is not a square, then three of its vertices will lie on the boundary of the polygon.

To prove, suppose that's not the case, i.e. that the maximum area rectangle is not a square, but only two of its vertices are on the boundary of the polygon. I'll show how to construct a bigger rectangle, contradicting the maximality.

Call the vertices of the rectangle A, B, C, and D. Without loss of generality, assume that B and D are the two that are on the polygon boundary. Since A and C are on the interior of the polygon, there's some wiggle room around them (represented with circles around A and C in the picture below). Now draw a circle around the rectangle, and slide points A and C a little bit around the circle by the same amount (to make A' and C', pictured below) so that the new rectangle A'BC'D is more square than the original rectangle. This process creates a new rectangle that is also within the original polygon and has a larger area. This is a contradiction, so the proof is done.

Constructing a new rectangle

To believe that proof, you have to convince yourself that the area of a rectangle inscribed in a circle increases as it becomes "more square" (i.e. the difference between the edge lengths gets smaller). You also need the polygon to be convex so that the new lines are all within it. And there are probably other little details getting swept under the rug, but I'm fairly sure they all work out.

share|improve this answer
    
Note #4 is fishy, because "wiggling" the two other vertices will create non-rectangles. –  whuber Oct 3 '13 at 14:25
    
True. However your visualization of the 4th example is not quite right (if 2 vertices are on the polygon boundary, you can't stretch it further). I can't find exactly how to explain it though (tried writing a comment but got too messy), but I trust you are right. –  Saryk Oct 3 '13 at 14:32
    
I believe there are counterexamples to note #4. The ones I have found take some involved calculation to show, though; the simplest is a perturbation of an irregular hexagon (a square with two opposite corners slightly cut off). –  whuber Oct 3 '13 at 15:05
    
Agreed that Note #4 is fishy. I'll take a closer look this evening and either fix it or remove it. –  csd Oct 3 '13 at 15:08
    
+1 That is a nice resolution of the difficulty. Thanks for the edit! –  whuber Oct 3 '13 at 20:49

Most other algorithms find the maximum area rectilinear rectangle inscribed in a convex polygon, and have a complexity of O(log n). I don't think your guess that the max area polygon is aligned with one of the sides is correct, because all you would need to do is rotate the polygon n times, resulting in a complexity of O(n log n), and in my brief research I couldn't find anything saying it was that easy.

However, this paper describes an approximation algorithm that will get you close to the right answer.

As best as I understand the algorithm, it builds on top of one of the known axis-aligned max area polygons, and then randomly samples points inside the polyon space, generates multiple axis from those random samples, iterates over those axis and applies the axis-aligned algorithm to each one, and then returns the biggest rectangle in that set.

share|improve this answer
    
Is there perhaps a typo in the first sentence? There cannot possibly be a O(log(n)) algorithm because merely reading in the coordinates is a O(n) operation! –  whuber Sep 30 '13 at 14:18

I have done a very quick and hideous sketch about your green note in the question. I couldn't post it as comment so I had to write an answer, even if it isn't one.
I believe that in the image below we have a maximum area rectangle (not perfect, it's just a sketch made on Paint to give an idea), and I don't think you can find a bigger one which would have a common side with the borders of the black plygon...
However I can be wrong, in that case you have all my apologies.
Quick Sketch I made on Paint

share|improve this answer
2  
Good point (+1). There's a much simpler counterexample, though: consider the problem of inscribing a maximal-area rectangle within a regular octagon. It's easy to see (and easy to prove by first finding a maximal square within the octagon's circumcircle) that the corners of the solution coincide with alternating vertices of the octagon and that this solution is substantially larger than any edge-aligned inscribed rectangle. –  whuber Oct 3 '13 at 14:21
    
Actually (I just have a big doubt right now), the external smallest rectangle (the ones from this post) of this polygon hasn't got the same orientation as one of the sides, has it ? (I would see it the same orientation as my red rectangle) –  Saryk Oct 3 '13 at 14:43
2  
That polygon isn't convex, by the way. The original question does restrict to convex polygons. –  csd Oct 3 '13 at 14:55
2  
@csd That's a great point, but Saryk is still correct, as my counterexample shows. Saryk, there is no problem with the minimum area bounding rectangle: it's easy to prove (rigorously) that it must include a side of the convex hull. I believe the maximum area inscribed rectangle (of a convex polygon) need only have two vertices touching the boundary, no more. –  whuber Oct 3 '13 at 15:03

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.