Divide grid so that each box has only one object

Question

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.

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!

Answer 1

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