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: Covering a Polygon with Rectangles
I am hoping to split up the questions so I can attract better answers.
Best Answer
Let $P$ be your polygon, $e$ an edge of $P$. I will interpret one aspect of your question as seeking all the maximal rectangles with one side flush with each $e$, each rectangle $R$ maximal in the sense that (a) $R \subset P$ but (b) there is no other rectangle $R' \subset P$ with $R' \supset R$. If you can solve this for one edge $e$, you can iterate over all $n$ edges of $P$.
Fix $e$ to be horizontal (by rotating $P$). Now your problem is to find the maximal axis-aligned rectangles flush with $e$. It is clear that $R$ is maximal only if all four sides of $R$ cannot be moved to enlarge $R$. The edge $e$ determines one side, so there are three to be blocked by $P$ from enlargement. A side of $R$ can be blocked by a vertex of $P$ lying in its interior, or two sides can be blocked by their common corner resting on an edge of $P$. Various possibilities are shown above. A naive $O(n^3)$ algorithm can search through all possible blockers for the three sides, yielding an $O(n^4)$ algorithm over all edges of $P$. From among these, you could select, e.g., those with largest area, or largest perimeter, or whatever criterion is relevant to your application.
This naive algorithm can be considerably sped up. A series of papers led to an $O(n \log^2 n)$ algorithm, which I think might still be the best available. Whether it would be worth implementing all the tricks necessary to reach this low time complexity is another question.
To address how to "continually cut [your] polygon down" requires some criterion to chose among all the options. What I describe above is just a start, identifying all the maximal rectangles. I suspect any choice you make will lead to an NP-hard problem, and you'll be forced into heuristics or approximation algorithms.
One heuristic is the greedy algorithm. Find, say, the largest-area maximal rectangle $R$ in $P$. Create several new polygons by subtracting $R$: $P \setminus R$. Recurse on the pieces. This would be easy to implement, and equally easy to thwart. :-)
Here is what I meant by thwarting the greedy algorithm:
Because no definition of what constitutes an optimal coverage by these rectangles has been detailed, I cannot prove the greedy algorithm fails to achieve optimality. But I am convinced that any reasonable definition of optimality will not always be achieved by the greedy algorithm.