I am looking for a good data structure for storing a set of points $P\subset \mathbb{N}^n$ that is able to answer the following query:

Given a point $x=(x_1,\cdots,x_n)$, does there exist a point $p = (p_1,\cdots,p_n)\in P$ such that $p \leq x$, meaning that $p_i\leq x_i$ for all $i\in \{1,\cdots, n\}$?
If the answer is yes, then the data structure should return one such point.

Ideally, it should be possible to dynamically add points to $P$.

The data structure can 'forget' a point $p \in P$ if there exists another point $p'$ with $p' \leq p$.

The use case that I am thinking about has 'small points'. Something like $x = (x_i)$ with $\sum_i x_i \leq 30$. But has a somewhat larger $n$.

ps: I have removed the copy on SO.

  • $\begingroup$ Oh, im sorry. I made a mistake. The first inequality i wrote was incorect. I will edit it $\endgroup$ – Ward Beullens Mar 31 '16 at 23:53
  • $\begingroup$ It sounds like you're looking for the so-called "layers of maxima" problem. $\endgroup$ – jbapple Apr 1 '16 at 0:10
  • 2
    $\begingroup$ Cross posted: stackoverflow.com/questions/36341739/… $\endgroup$ – jbapple Apr 1 '16 at 0:22
  • $\begingroup$ Thanks, this helps me. I will be reading about this. Though i think the problems are not exactly the same. The maxima problem computes the set of undominated points, whereas i am looking for a point that dominates a certain point if it exists. $\endgroup$ – Ward Beullens Apr 1 '16 at 0:30
  • $\begingroup$ I was not aware that this was explicitly prohibited, I won't do it again. I removed the question from stack overflow since there where no usefull answers there. $\endgroup$ – Ward Beullens Apr 1 '16 at 13:41

What about first computing the skyline (a.k.a. maximal vectors, etc.) of all points, then maintain a data structure for orthogonal range reporting?

The range you are interested in is the orthant with coordinates smaller in all dimensions below your query point.

Actually what you are looking for is a dynamic orthogonal range reporting datastructure. But I add the skyline in case you want to prune the set $P$ first (this answers the part you wrote about 'forgetting' point $p$ if there is some $p'\leq p$).

  • $\begingroup$ Do you happen to know if there is a version of a dynamic orthogonal range reporting datastructure that is easy enough to understand and implement for someone who is not specialized in CS? (that would be me) $\endgroup$ – Ward Beullens Apr 25 '16 at 11:08
  • $\begingroup$ No, I do not know the alternatives well enough to advise a specific solution. The $kd$-tree is very simple, but it does not seem appropriate for large $n$ and has weak guarantees, so it is probably a poor option there. $\endgroup$ – Joseph Stack Apr 25 '16 at 13:24
  • $\begingroup$ Yeah, according to wikipedia you should only use kd-trees if the number of datapoints is larger than $2^n$, since I am looking to use it for $n \sim 100$ this won't be the case. $\endgroup$ – Ward Beullens Apr 25 '16 at 13:39
  • $\begingroup$ Thanks for your help. I am thinking about just maintaining a lexicographically sorted list of the 'skyline' and searching it using backtracking. Inserting points would be O(log(|P|) ). I Think querrying would be exhaustive search in the worst case, but I hope that on average it would do much better. Any thoughts? $\endgroup$ – Ward Beullens Apr 25 '16 at 13:53
  • 1
    $\begingroup$ No further thought. Perhaps you could accept the answer as the literature provides a solution so this is not an 'open question' anymore :) $\endgroup$ – Joseph Stack Apr 28 '16 at 8:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.