2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Oh, im sorry. I made a mistake. The first inequality i wrote was incorect. I will edit it $\endgroup$
    – Ward Beullens
    Mar 31, 2016 at 23:53
  • $\begingroup$ It sounds like you're looking for the so-called "layers of maxima" problem. $\endgroup$
    – jbapple
    Apr 1, 2016 at 0:10
  • 2
    $\begingroup$ Cross posted: stackoverflow.com/questions/36341739/… $\endgroup$
    – jbapple
    Apr 1, 2016 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, 2016 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, 2016 at 13:41

1 Answer 1

Reset to default
1
$\begingroup$

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$).

Improve this answer
$\endgroup$
5
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 8:09

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.

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