I'm looking for an algorithm to find a set of largest inscribed rectangles of a concave polygon where each rectangle must be collinear with one of the edges of the polygon.

In other words, I want to continually cut my polygon down using rectangles until I am left with regions were the largest-inscribed rectangle is not sharing an edge with the original polygon.

Is there a known algorithm for this?

An example:

This post is related to another post: Cover a Concave Polygon with a minimum number of rectangles

I am hoping to split up the questions so I can attract better answers.

  • $\begingroup$ Are you trying to find the largest single rectangle (as described in the first paragraph), or are you trying to find an optimal set of rectangles (as described in the second paragraph)? The two problems are very different. $\endgroup$
    – Jeffε
    Aug 29, 2012 at 14:10
  • $\begingroup$ @JɛffE If I take a greedy approach of finding the largest single rectangle and use that rectangle to parition my polygon, I can iteratively perform this to get the set. Or, at least I think... $\endgroup$
    – Josh C.
    Aug 29, 2012 at 14:23
  • 1
    $\begingroup$ But which problem are you really interested in? The greedy algorithm is unlikely to give you the optimal set (although it might be a reasonable approximation). $\endgroup$
    – Jeffε
    Aug 29, 2012 at 21:40
  • $\begingroup$ @JɛffE, Maybe I don't understand what I am asking. I don't think I stated the solution need be optimal. Did I miss something? $\endgroup$
    – Josh C.
    Aug 29, 2012 at 22:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.