2
$\begingroup$

Is there an efficient algorithm to divide a 2D space, which contains several different sized rectangles, such that each partition has only a single object. Please see the attached image. box with partitions

I have come up with a recursive algorithm that cycles through the 2 axis and divide the boxes until there is only one object in a box/partition. The only problem is that the arrangement that I have in mind is actually inefficient and it seems very hard to handle cases in which the rectangles are overlapping. In the case where the rectangles are overlapping, we want all the overlapping rectangles to be inside the same partition.

Another detail, the boxes will always be axis aligned and the partitions also have to be axis aligned.

Any help will be greatly appreciated. Thank you!

$\endgroup$
  • 1
    $\begingroup$ If the rectangles are overlapping the problem is obviously impossible, not just 'very hard'. Are all rectangles always axis-aligned, and should the partitions be as well? $\endgroup$ – orlp Aug 5 at 9:54
  • $\begingroup$ Sorry about missing out on that information. So if the boxes are overlapping there should be a single partition covering all those boxes. Sorry about that. $\endgroup$ – Tez_Nikka Aug 7 at 23:15
0
$\begingroup$

I initially missed your remark about overlapping rectangles -- as orlp said in a comment, there's obviously no solution in those cases. But I had already typed the rest of this answer out, assuming the input has no overlapping rectangles, so I'll leave it here in case it's helpful.

It sounds like your current method repeatedly looks for a guillotine cut: That is, a cut that goes all the way from top to bottom, or all the way from left to right.

Unfortunately, even if you split subproblems at as many places as possible within a single $O(n \log n)$-time scan along one dimension, this can result in $O(n^2 \log n)$ time overall, like for instances such as the following where each scan only succeeds in peeling off a single rectangle:

XXXXX

X   X
X X X
X
X XXX

But the real problem is that some instances can't be solved this way at all, even when no overlapping rectangles are involved. For example:

XXX X
    X
X   X
X
X XXX
$\endgroup$

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.