Finding the bounds of an area covered by n of m rectangles

Question

I have a set of m non-rotated, integer (pixel) aligned rectangles, each of which may or may not overlap. The rectangles cover thousands of pixels. I need to find the minimum sized bounding box that covers all areas that are covered by n of the m rectangles.

A (dirty) way of doing this is to paint a canvas that covers the area of all the targets. This is O(mk) where m is the number of rectangles and k is the number of pixels per rectangle. However since k is much greater than m I think there is a better solution out there.

This feels like a dynamic programming problem...but I am having trouble figuring out the recursion.

Solution which is better but still not great:

Sort the start and end points of all the rectangles in the X direction O(mlogm), iterate and find the x positions that may have over n rectangles, O(m) loop. For each x position that may have over n rectangles, take the rectangles at that position and sort the starts and stops at that position (O(mlogm)). Find the region of overlap, keep track of the bounds that way. Overall, O(m^2logm).

Answer 1

Hello MadScienceDreams,

Just to clarify, the bounding box is also non-rotated, correct?

If this is the case, then just keep track of the four variables: minX, maxX, minY, maxY–representing left-most, right-most, top-most, and bottom-most pixels–that define the bounding box, loop through each of the rectangles updating the four variables, and defining the new bounding box given those four variables.

EDIT

It looks like you are asking about finding the bounds of some subset of rectangles, not the whole set.

So you have M rectangles, and you choose N rectangles from them, and find the bounds within that.

Even in this situation, looping through the N rectangles and keeping track of their bound would be at most O(m), which isn't bad at all.

I feel that I must be misunderstanding your question since this response isn't what you are probably looking for; is your question actually trying to ask how to precompute the bounds so that given any subset, know the total bounds in constant time?