Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

cuom1999's blog

Decompose union of rectangles
By cuom1999, history, 4 years ago, In English

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?

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What do you want if there are several decompositions into non-overlapping rectangles? I mean usually there are plenty. I assume you want as few rectangles as possible. It doesn't look trivial to me why your first approach would be optimal. The decomposition is clearly not unique (not even the optimal one, take (0, 0), (1, 2) and (0, 0), (2, 1))

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any decomposition is fine. I'm only interested in the number of output rectangles and the running time.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +32 Vote: I do not like it

      Do you want the output rectangles to be non-overlapping? If so I think it might require n^2 rectangles in the answer, and the scanline would be asymtotically optimal.

      For instance, consider the case of O(n) rectangles forming a 2d grid, like this:

      .X.X.X.X.X.
XXXXXXXXXXX
.X.X.X.X.X.
XXXXXXXXXXX
.X.X.X.X.X.
XXXXXXXXXXX
.X.X.X.X.X.

      I don't think that is even possible to represent in fewer than O(n^2) rectangles...

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Nice, this is what I'm looking for. Thanks!

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

if i meet it as task i would just use a quadtree. we build a quadtree keeping rectangles inside vertexes and just recursively merge them without overlapping UPD: oh i think it doesn't work

→ Reply