# Efficiently representing sets of $n$-dimensional rectangles orthogonal an axis

Is there a data structure that allows one to represent sets of $n$ dimensional rectangles, all orthogonal or parallel to the $x$ axis. efficiently. Allowing all common set operations (union, difference etc) to be done efficiently as well?

Let me explain what I mean by a 2D example.

Given this two set of rectangles * is the first set % is the second set

*************
*           *
*       %%%%o%%%%%%
*       %   *     %
********o ***     %
%         %
%%%%%%%%%%%


If I'll do * union %, I can get

*************
*           *
*******************
*                 *
*******************
*         *
***********


or

*************
*           *
*******************
*       *   *     *
*******************
*         *
***********


If I'll do * difference %, I can get

*************
*           *
*************
*       *
*********


Can you refer me to a relevant paper?

• What does "supporting union" mean if you're maintaining a set of rectangles? The union of two rectangles is not a rectangle. Nov 30, 2011 at 20:19
• Are your rectangles tilted in any which manner, or nice and orthogonal? Nov 30, 2011 at 20:41
• @ChadBrewbaker excellent question. None are tilted, all are orthogonal or parallel to the X axis. Dec 1, 2011 at 4:42
• Again, I'm still not sure exactly what you want. Writing "data structure" suggests that you want to store a set of boxes and efficiently answer certain queries about that set and/or perform operations to modify that set. Do you just mean "algorithm"? Dec 1, 2011 at 16:19
• Also: the union or difference of two n-dimensional boxes can be partitioned into at most 3n n-dimensional boxes in $O(n^2)$ time using the standard array representation $[min_1, max_1, min_2, max_2 \dots, min_n, max_n]$, by considering one dimension at a time. Moreover, a partition of the union or difference of two n-dimensional boxes may require $\Omega(n)$ pieces, each represented by 2n numbers, so $O(n^2)$ time is worst-case optimal with that representation. Do you want something better? Dec 1, 2011 at 16:22