# Data structure for storing points and finding a predecessor of a point

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.

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

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$).
• 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. – Joseph Stack Apr 25 '16 at 13:24
• 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. – Ward Beullens Apr 25 '16 at 13:39