Given a rectilinear polygon, what is an run-time efficient algorithm that finds the largest inscribed rectangle the sides of which either parallel or perpendicular to the sides of the rectilinear polygon? A dumb algorithm to form all the rectangles formed from unordered 4-tuples of the edges, for each of the rectangle check to see if any edge or vertex lies inside it, then choose the one with the largest area. The run time is quintic.
8
-
$\begingroup$ Would it not make more sense to wait for an answer to this former question of yours, which seems to be a special case of this one, with a certain chance that an answer to it may also solve this more general case? In the current form, I would not be astonished if the community closes one of it as a duplicate. $\endgroup$– Doc BrownCommented Jun 9, 2021 at 6:50
-
$\begingroup$ @DocBrown: Actually these two questions are different and one is not a special case of the other. $\endgroup$– HansCommented Jun 9, 2021 at 7:08
-
$\begingroup$ 1. What counts as "run-time efficient"? Polynomial time? If so, doesn't the "dumb algorithm" from that problem solve this one in quadratic time, too? 2. I have the impression the usual term for such rectangles is "axis-aligned". $\endgroup$– D.W. ♦Commented Jun 9, 2021 at 7:16
-
$\begingroup$ Ok, would you mind to explain me the difference? Isn't the rectangle R in your earlier question a special case of a region partionable into rectangles of the described form? $\endgroup$– Doc BrownCommented Jun 9, 2021 at 8:59
-
$\begingroup$ By region partitionable into rectangles fo you mean a rectilinear polygon? I'm guessing the inscribed rectangle doesn't have to be part of the partition right? $\endgroup$– TassleCommented Jun 9, 2021 at 11:49
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
2
Daniels, Milenkovic and Roth [1] show how this can be done in $O(n\log^2 n)$ time ($n$ being the number of vertices) even for general polygons (possibly with holes). They also mention that the algorithm from Aggarwal and Suri [2] for largest empty rectangle can be adapted to your problem in the rectilinear case, but I haven't thought about how one would do that.
[1] Daniels, Milenkovic and Roth. Finding the largest area axis-parallel rectangle in a polygon. https://www.sciencedirect.com/science/article/pii/0925772195000410
[2] Aggarwal and Suri. Fast algorithms for computing the largest empty rectangle. https://dl.acm.org/doi/10.1145/41958.41988
-
$\begingroup$ +1. I will wait a while before accepting your answer so that others may chime in as well. Would you be interested in looking at this question cs.stackexchange.com/q/141143/20543? $\endgroup$– HansCommented Jun 9, 2021 at 16:01
-
$\begingroup$ @Hans I took a look at it but haven't figured out a way to do better than looking at all pairs of corners :/ $\endgroup$– TassleCommented Jun 10, 2021 at 21:18
$\begingroup$
$\endgroup$
2
After seeing @Tassle's answer, I did a bit Google search and found that the largest empty rectangle is a well researched subject.
In the following, I try to draft an algorithm on my own.
Suppose the polygon has $2n$ sides. There has to be $n$ horizontal and $n$ vertical sides. For simplicity sake, we assume no two horizontal sides of the rectilinear polygon have the same $y$ coordinates, and the same for the vertical sides. A candidate rectangle has to have all its sides coincide with the sides of the rectilinear polygon. Given the top and bottom sides of the candidate rectangle, the left and right sides are determined or the candidate rectangle does not exist. So we need to examine at most $\displaystyle n\choose 2$ candidate rectangles. The complexity of this algorithm is at least quadratic.