Hi Volmer,
Yes, you understand the problem exactly - I want the output list to consist of as few non-overlapping rectangles as possible that describe the same shape as the original did.
This implies that if the original list contains no overlapping rectangles, the output list will be pretty much the same (although the order may be different, of course).
A simple case would be as follows:
Input List:
Rectangle 1 TopLeft = 10, 10; BotRight = 90, 50
Rectangle 2 TopLeft = 10, 30; BotRight = 90, 70
The ideal algorithm would actually generate a single rectangle from the above list with TopLeft = 10, 10 and BotRight = 90,70.
Now imagine a slightly different inpuit list
Rectangle 1 TopLeft = 10, 10; BotRight = 90, 50
Rectangle 2 TopLeft = 20, 30; BotRight = 100, 70
The same algorithm would generate 3 rectangles by splitting at the overlap:
Rectangle 1' TopLeft = 10, 10; botRight = 90, 30
Rectangle 2' TopLeft = 10, 30; botRight = 100, 50
Rectangle 3' TopLeft = 50, 30; botRight = 100, 70
I've scribbled a few ideas down also but I cant find anything that doesnt require each rectangle to be tested against the others and hence have O(n*n) complexity...