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!