Arbitrary partition of a rectangle into rectangles: algorithms and data structures

Question

(This is a purely curiosity question, and is maybe more about computer science than mathematics, but anyway.)

Suppose we're given a set of (at least two) $n$-dimensional intervals

$$I_k := \{x | a_k \leqq x \leqq b_k\}\text{ where }k = 0, 1, \dots, p$$

here $a_k \leqq b_k$, and otherwise $a_k$ and $b_k$ are arbitrary vectors in $\mathbb R^n$, also $x \leqq y := \forall i, x^i \leq y^i$.

For $n = 1, 2, 3$, these intervals represent the usual (closed) intervals, coordinate parallelograms, and coordinate parallelepipeds respectively; we're most interested in the case of rectangles: $n = 2$ and the orthonormal coordinates.

• Is there an effective algorithm to check that all $I_k$ for $k=1,\dots,p$ together form a partition of $I_0$?
• Maybe a data structure, less redundant than just the set?

---

The motivation is in 2D computer graphics: widgets packing, tiling window management, etc. All the software I've seen uses grid-of-grids approach, but there are partitions that don't fit in this scheme (say, a square, surrounded by four rectangles, to form a larger square). So grid-of-grids/table-of-tables is not quite general description, but I'm curious which are, and maybe the best starting point is the math. part.

---

Currently I'm thinking about somehow tracking the corners, progressively, starting from a given one of $I_0$; with the help of $\min$ and $\max$ operations, induced by this vector relation.

Yet I suspect $I_0$ needs not a special treatment, since it simply denotes an "inverted" interval, exterior, with the negative volume. And there might be more than one such interval. So the whole set of $I_k$'s may be seen as forming a partition of the whole space, in a sense, into the $p$ intervals.

This problem seems to be more difficult than I thought. May be related:

• Rectangular Layouts and Contact Graphs

• Directed Graphs and Rectangular Layouts

Answer 1

Make record of corners, at start its a₀ which ends at b₀
You can put rectangle in corner if a_i=c[a] and b_i≦c[b]
When you put rectangle in a corner you make new corners or change existing corners. Depends on if the rectangle you put is on the lane with an existing corner... pretty complicated
Some algorithm would be as this: Run through all coordinates of b_i and if b_i^k<c[b]^k then create new corner which starts at point a=c[a] but with k-th coordinate replaced to b_i^k and ends at point b=b_i but k-th coordinate replaced to c[b]^k.
But if b_i^k=c[b]^k then you wanna check if maybe some corner got bigger now like in the example on this image, when you put green rectangle in corner c1 corner c2 now has one longer side. You check this by running through all corners and check if c_j[a] has all coordinates but one same as b_i; and then replace that coordinate in c_j[b]
In the end you remove the corner and the rectangle form the lists and repeat it

If in one moment there is no more corners and rectangles, both, then it's true, otherwise false