0
$\begingroup$

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.

$\endgroup$
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 Brown Jun 9 at 6:50
  • $\begingroup$ @DocBrown: Actually these two questions are different and one is not a special case of the other. $\endgroup$ – Hans Jun 9 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. Jun 9 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 Brown Jun 9 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$ – Tassle Jun 9 at 11:49
2
$\begingroup$

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

$\endgroup$
2
  • $\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$ – Hans Jun 9 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$ – Tassle Jun 10 at 21:18
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It looks like you assume, that left and right sides can be found in constant time. I think, that needs to be elaborated. $\endgroup$ – HEKTO Jun 12 at 13:55
  • $\begingroup$ @HEKTO: Good question. I will look into this. $\endgroup$ – Hans Jun 14 at 1:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.