<p>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. </p>

<p>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.</p>

<p>Is there a known algorithm for this? </p>

<p>An example:</p>

<p><img src="https://i.sstatic.net/Yz7fT.png" alt=""></p>

<p>This post is related to another post: <a href="https://cstheory.stackexchange.com/questions/12376/">Cover a Concave Polygon with a minimum number of rectangles</a></p>

<p>I am hoping to split up the questions so I can attract better answers.</p>

CC BY-SA 3.0
2012-08-29T14:10:31.110Z
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.
Jeffε
CC BY-SA 3.0
2012-08-29T14:23:03.760Z
@JɛﬀE 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...
Josh C.
CC BY-SA 3.0
2012-08-29T21:40:09.413Z
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).
Jeffε
CC BY-SA 3.0
2012-08-29T22:09:30.677Z
@JɛﬀE, Maybe I don't understand what I am asking. I don't think I stated the solution need be optimal. Did I miss something?
Josh C.
<co.combinatorics><cg.comp-geom>
Get Largest Inscribed Rectangle of a Concave Polygon
Josh C.
# Get Largest Inscribed Rectangle of a Concave Polygon

(Asked by: username_0 on 2012-08-29)

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:

![](https://i.sstatic.net/Yz7fT.png)

This post is related to another post: [Cover a Concave Polygon with a minimum number of rectangles](https://cstheory.stackexchange.com/questions/12376/)

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

**Tags:** co.combinatorics, cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_0**: @JɛﬀE 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...  
> **username_1**: 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).  
> **username_0**: @JɛﬀE, Maybe I don't understand what I am asking. I don't think I stated the solution need be optimal. Did I miss something?  

---

## 0 answers

