<p>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?</p>

<p>Let me explain what I mean by a 2D example.</p>

<p>Given this two set of rectangles <code>*</code> is the first set <code>%</code> is the second set</p>

<pre><code>*************
*           *
*       %%%%o%%%%%%
*       %   *     %
********o ***     %
        %         %
        %%%%%%%%%%%
</code></pre>

<p>If I'll do <code>*</code> union <code>%</code>, I can get</p>

<pre><code>*************
*           *
*******************
*                 *
*******************
        *         *
        ***********
</code></pre>

<p>or</p>

<pre><code>*************
*           *
*******************
*       *   *     *
*******************
        *         *
        ***********
</code></pre>

<p>If I'll do <code>*</code> difference <code>%</code>, I can get</p>

<pre><code>*************
*           *
*************
*       *
*********
</code></pre>

<p>Can you refer me to a relevant paper?</p>

CC BY-SA 3.0
2011-11-30T20:19:38.630Z
What does "supporting union" mean if you're maintaining a set of rectangles?  The union of two rectangles is not a rectangle.
Jeffε
CC BY-SA 3.0
2011-11-30T20:41:34.270Z
Are your rectangles tilted in any which manner, or nice and orthogonal?
Chad Brewbaker
CC BY-SA 3.0
2011-12-01T04:42:31.750Z
@ChadBrewbaker excellent question. None are tilted, all are orthogonal or parallel to the X axis.
Chi-Lan
CC BY-SA 3.0
2011-12-01T05:23:35.323Z
@Chi-Lan could you clarify JeffE's question ? What is the desired output when you perform a union operation ?  or a difference ?
Suresh Venkat
CC BY-SA 3.0
2011-12-01T06:11:03.137Z
@JɛﬀE just a guess, but maybe he means set union of the sets of rectangles, where the rectangles in the set are allowed to overlap. BTW is an "n-dimensional rectangle" a box?
Sasho Nikolov
CC BY-SA 3.0
2011-12-01T09:17:30.820Z
@SureshVenkat A set of rectangles orthogonal to the axis can remains a set rectangles after union or difference (you might have to split a rectangle into four rectangles, but it's still representable as a set of rectangles). I'll try to expand in the question.
Chi-Lan
CC BY-SA 3.0
2011-12-01T14:54:11.320Z
This is a partial answer. R Tree(http://en.wikipedia.org/wiki/R_tree) supports some of the operations; insertion, deletion and search(does not support union etc). Seems to perform well in practice. I am unaware what theoretical guarantees it has.
Ashwinkumar B V
CC BY-SA 3.0
2011-12-01T16:19:53.413Z
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"?
Jeffε
CC BY-SA 3.0
2011-12-01T16:22:31.910Z
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?
Jeffε
CC BY-SA 3.0
2011-12-01T19:38:26.103Z
@JɛﬀE, I want a data structure, that will allow me to do the union difference and intersection as quickly as possible, and to find later if a certain point is contained in one of the rectangles. I want something that performs better, say. in the case that there are less than $O(n^2)$ boxes.
Chi-Lan
CC BY-SA 3.0
2011-12-02T11:03:48.147Z
Let me try again.  What precisely should a union operation do to your data structure?  Do you mean "Given data structures representing two orthogonal polyhedra $X$ and $Y$, compute a data structure that represents the orthogonal polyhedron $X\cup Y$."?
Jeffε
CC BY-SA 3.0
2011-12-03T18:37:04.153Z
@JɛﬀE, yes, and of course also $X\cap Y$, and $X\setminus Y$. Assuming that an orthogonal polyhedra is a polyhedra (not necessaryly connected) whose all edges are parallel of orthogonal to the `X` axis. (Thanks for trying, sorry I'm not clear enough).
Chi-Lan
<cg.comp-geom>
Efficiently representing sets of $n$-dimensional rectangles orthogonal an axis
Chi-Lan
# Efficiently representing sets of $n$-dimensional rectangles orthogonal an axis

(Asked by: username_0 on 2011-11-30)

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?

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: What does "supporting union" mean if you're maintaining a set of rectangles?  The union of two rectangles is not a rectangle.  
> **username_2**: Are your rectangles tilted in any which manner, or nice and orthogonal?  
> **username_0**: @ChadBrewbaker excellent question. None are tilted, all are orthogonal or parallel to the X axis.  
> **username_3**: @Chi-Lan could you clarify JeffE's question ? What is the desired output when you perform a union operation ?  or a difference ?  
> **username_4**: @JɛﬀE just a guess, but maybe he means set union of the sets of rectangles, where the rectangles in the set are allowed to overlap. BTW is an "n-dimensional rectangle" a box?  
> **username_0**: @SureshVenkat A set of rectangles orthogonal to the axis can remains a set rectangles after union or difference (you might have to split a rectangle into four rectangles, but it's still representable as a set of rectangles). I'll try to expand in the question.  
> **username_5**: This is a partial answer. R Tree(http://en.wikipedia.org/wiki/R_tree) supports some of the operations; insertion, deletion and search(does not support union etc). Seems to perform well in practice. I am unaware what theoretical guarantees it has.  
> **username_1**: 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"?  
> **username_1**: 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?  
> **username_0**: @JɛﬀE, I want a data structure, that will allow me to do the union difference and intersection as quickly as possible, and to find later if a certain point is contained in one of the rectangles. I want something that performs better, say. in the case that there are less than $O(n^2)$ boxes.  
> **username_1**: Let me try again.  What precisely should a union operation do to your data structure?  Do you mean "Given data structures representing two orthogonal polyhedra $X$ and $Y$, compute a data structure that represents the orthogonal polyhedron $X\cup Y$."?  
> **username_0**: @JɛﬀE, yes, and of course also $X\cap Y$, and $X\setminus Y$. Assuming that an orthogonal polyhedra is a polyhedra (not necessaryly connected) whose all edges are parallel of orthogonal to the `X` axis. (Thanks for trying, sorry I'm not clear enough).  

---

## 0 answers

