Arbitrary partition of a rectangle into rectangles: algorithms and data structures (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
 A: Make record of corners, at start its a0 which ends at b0
You can put rectangle in corner if ai=c[a] and bi≦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 bi and if bik<c[b]k then create new corner which starts at point a=c[a] but with k-th coordinate replaced to bik and ends at point b=bi but k-th coordinate replaced to c[b]k.
But if bik=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 cj[a] has all coordinates but one same as bi; and then replace that coordinate in cj[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 
