<p>For the following, $(w,x) &gt;= (y,z)$ iff $w &gt;= y$ and $x &gt;= z$.</p>

<p>I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$.  Each point has an associated set.  I would like a data structure that can perform the following:</p>

<p>$include(x,y,i)$ - include the element $i$ to all of the sets associated with a point $p$, where $p &gt;= (x,y)$</p>

<p>$remove(x,y,i)$ - remove the element $i$ from all of the sets associated with a point $p$, where $p &gt;= (x,y)$</p>

<p>$retrieve(x,y)$ - retrieve the set associated with point $p = (x,y)$</p>

<p>My intuition is telling me that $include$ and $remove$ should be possible in something like $\text{polylog}(k)$ and $retrieve$ should be possible in something like $\text{polylog}(k) \times (\text{size of set})$.  The 2-dimensional aspect of this is stumping me, however.</p>

<p>Motivation: this data structure could be very useful for quickly calculating edit distances for a data set I'm using at work.</p>

CC BY-SA 3.0
2014-10-13T02:19:31.467Z
1. Have you looked at standard 2-D data structures, e.g., k-d trees, binary space partitioning trees, etc.?  2. Can we assume all of the include()/remove() operations come before any retrieve()?  If so, there is a clean answer.  Scan by increasing $x$-value, from $x=-\infty$ to $x=+\infty$.  Build a segment tree/interval tree, initially empty, containing all of the points to the left of the current $x$-value.  As you scan rightwards, each time you encounter a point, add it to the tree.  Now if you use a persistent binary tree, you can handle retrieve() calls efficiently.
D.W.
CC BY-SA 3.0
2014-10-14T11:34:37.203Z
@D.W. Thank you for your response. I had not thought of k-d trees and I believe they solve the problem. Unfortunately, the retrieves are mixed in with the includes and removes, so I do not think that your 2nd suggestion will work in my situation.
bbejot
<ds.algorithms><ds.data-structures><dynamic-algorithms>
2-dimensional dynamic set retrieval
bbejot
# 2-dimensional dynamic set retrieval

(Asked by: username_0 on 2014-10-10)

For the following, $(w,x) >= (y,z)$ iff $w >= y$ and $x >= z$.

I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$. Each point has an associated set. I would like a data structure that can perform the following:

$include(x,y,i)$ - include the element $i$ to all of the sets associated with a point $p$, where $p >= (x,y)$

$remove(x,y,i)$ - remove the element $i$ from all of the sets associated with a point $p$, where $p >= (x,y)$

$retrieve(x,y)$ - retrieve the set associated with point $p = (x,y)$

My intuition is telling me that $include$ and $remove$ should be possible in something like $\text{polylog}(k)$ and $retrieve$ should be possible in something like $\text{polylog}(k) \times (\text{size of set})$. The 2-dimensional aspect of this is stumping me, however.

Motivation: this data structure could be very useful for quickly calculating edit distances for a data set I'm using at work.

**Tags:** ds.algorithms, ds.data-structures, dynamic-algorithms
> **Comments:**
> **username_1**: 1. Have you looked at standard 2-D data structures, e.g., k-d trees, binary space partitioning trees, etc.?  2. Can we assume all of the include()/remove() operations come before any retrieve()?  If so, there is a clean answer.  Scan by increasing $x$-value, from $x=-\infty$ to $x=+\infty$.  Build a segment tree/interval tree, initially empty, containing all of the points to the left of the current $x$-value.  As you scan rightwards, each time you encounter a point, add it to the tree.  Now if you use a persistent binary tree, you can handle retrieve() calls efficiently.  
> **username_0**: @D.W. Thank you for your response. I had not thought of k-d trees and I believe they solve the problem. Unfortunately, the retrieves are mixed in with the includes and removes, so I do not think that your 2nd suggestion will work in my situation.  

---

## 0 answers

