0
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ What does "supporting union" mean if you're maintaining a set of rectangles? The union of two rectangles is not a rectangle. $\endgroup$
    – Jeffε
    Nov 30, 2011 at 20:19
  • $\begingroup$ Are your rectangles tilted in any which manner, or nice and orthogonal? $\endgroup$
    – Chad Brewbaker
    Nov 30, 2011 at 20:41
  • $\begingroup$ @ChadBrewbaker excellent question. None are tilted, all are orthogonal or parallel to the X axis. $\endgroup$
    – Chi-Lan
    Dec 1, 2011 at 4:42
  • 1
    $\begingroup$ 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"? $\endgroup$
    – Jeffε
    Dec 1, 2011 at 16:19
  • 1
    $\begingroup$ 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? $\endgroup$
    – Jeffε
    Dec 1, 2011 at 16:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.