Decompose union of rectangles

Revision en1, by cuom1999, 2020-06-26 01:27:27

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?

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 cuom1999 2020-06-26 01:27:27 1288 Initial revision (published)