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