10
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
13
$\begingroup$

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$.
     Rectangles in a polygons

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.
 Daniels Fig.1

K. Daniels, V. Milenkovic, and D. Roth. Finding the largest area axis-parallel rectangle in a polygon. Comput. Geom. Theory Appl., 7:125-148, 1997. (CiteSeer link) Fig.1 shown above.

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:
     Greedy vs. Non
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ At first I didn't understand how the greedy algorithm might be easy to thwart. Now, I'll verture to take a guess: By greedy, we are considering the rectangle which maximizes my value for the first edge. If this is true, I would need to change that to iterate over all edges choosing the rectangle which maximizes my value before subtraction. (By the way, is this problem called Largest Empty Rectangle?) $\endgroup$
    – Josh C.
    Commented Aug 30, 2012 at 14:31
  • $\begingroup$ Also, I am a bit confused how to describe a function to conclusively maximize my rectangle's value when a corner is constrained by an edge instead of two vertices. Would this be a good approach? Take E and extend it until it intersects with two other edges of P. Then, orthogonal to E at each end find two new points, where each point lies on an edge of P or the edges connecting those points to E or to each other is constrained by a vertex of P. $\endgroup$
    – Josh C.
    Commented Aug 30, 2012 at 14:39
  • $\begingroup$ Also, to ensure that my extension of E does not intersect P by leaving P, is proximity a good check? In other words, if E intersects P more than two times, I should check the proximity of those intersections to the original end points of E. $\endgroup$
    – Josh C.
    Commented Aug 30, 2012 at 14:43
  • $\begingroup$ @JoshC: 1st question: See my added examples above re thwarting the greedy algorithm. 2nd question: When two adjacent corners are both constrained by edges, there is a continuum of maximal rectangles, from which you could select, say, the maximal area rectangle. 3rd question: You need a Boolean function that returns True iff rectangle $R \subset P$. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 31, 2012 at 23:36
  • $\begingroup$ Is there a name for an algorithm which subrtracts R from P? $\endgroup$
    – Josh C.
    Commented Nov 2, 2012 at 15:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .