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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Oct 13 '14 at 2:19
  • $\begingroup$ @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. $\endgroup$
    – bbejot
    Oct 14 '14 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.