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 '12 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 '12 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 '12 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 '12 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.