I'm thinking about this problem: Given $$$n$$$ rectangles on a unit grid with coordinates around $$$10^9$$$. We want to decompose the union of them into non-overlapping rectangles. There are two interests: the number of output rectangles and the running time. Here is one of my approaches:

Process rectangles one by one. We keep a list of processed non-overlapping rectangles. For a newly added rectangle, we iterate over the list and find one that intersects our new rectangle. If there is, we divide the new rectangles into 4 small parts and process them recursively. This approach depends on the size of the result; so if there are $$$k$$$ output rectangles, the running time seems to be around $$$O(nk)$$$. In random test cases, $$$k \approx O(n)$$$. And it seems to be very hard to generate a counter test since we could shuffle the order of rectangles first.

I'm also thinking about scanline but haven't figured out how to get a good number of output rectangles. The best thing I came up with would result $$$O(n \log n)$$$ time complexity but may contain $$$O(n^2)$$$ rectangles in the worst cases, which is easy to generate counter tests.

I also tried googling but the closest thing I found is partitioning a polygon. Would you share some thoughts on this problem?