I have a 2 dimension cyclic space made of unit squares, and a list of rectangles made of these unit squares in that space. The space size is of the form (2^n; 2^n) and the rectangles are sections of that space.
I'm looking for an algorithm to determine a list with the smallest number of rectangles covering the same area than the previous list.
The rectangles in the first list can be overlapping The same is possible for the result list.
I was thinking of giving the rectangle a starting point and a length for each direction:
This one would be ((2;1); 3; 1) in a space of size (4; 4) for example:
For the time being, all I can see is to check every rectangle to each other in the purpose to shave them until complete deletion, then fusion them to make rectangle disappear, but I'm not even sure it work.
Due to the sheer size of the space and the fact that in the worst case, the biggest rectangle will have a size of half the space, using matrix or table isn't a viable option, since my goal is to find an algorithm in polynomial time at most, and maybe a general solution for n dimensions.