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

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

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

CC BY-SA 3.0
2016-04-25T11:08:33.793Z
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)
Ward Beullens
CC BY-SA 3.0
2016-04-25T13:24:19.090Z
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
CC BY-SA 3.0
2016-04-25T13:39:48.243Z
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
CC BY-SA 3.0
2016-04-25T13:53:17.387Z
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?
Ward Beullens
CC BY-SA 3.0
2016-04-28T08:09:57.250Z
No further thought. Perhaps you could accept the answer as the literature provides a solution so this is not an 'open question' anymore :)
Joseph Stack
CC BY-SA 3.0
2016-04-25T10:48:51.500Z
2016-04-25T10:48:51.500Z
Joseph Stack
<p>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:</p>

<blockquote>
  <p>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\}$?<br>
  If the answer is yes, then the data structure should return one such point.</p>
</blockquote>

<p>Ideally, it should be possible to dynamically add points to $P$.</p>

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

<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$.</p>

<p>ps: I have removed the copy on SO.</p>

CC BY-SA 3.0
2016-03-31T23:53:40.460Z
Oh, im sorry. I made a mistake. The first inequality i wrote was incorect. I will edit it
Ward Beullens
CC BY-SA 3.0
2016-04-01T00:10:03.507Z
It sounds like you're looking for the so-called "layers of maxima" problem.
jbapple
CC BY-SA 3.0
2016-04-01T00:22:48.867Z
Cross posted: http://stackoverflow.com/questions/36341739/data-structure-for-storing-points-and-finding-lower-points
jbapple
CC BY-SA 3.0
2016-04-01T00:30:03.903Z
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
CC BY-SA 3.0
2016-04-01T13:41:21.903Z
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
<ds.data-structures><high-dimensional-geometry>
Data structure for storing points and finding a predecessor of a point
Ward Beullens
# Data structure for storing points and finding a predecessor of a point

(Asked by: username_0 on 2016-03-31)

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.

**Tags:** ds.data-structures, high-dimensional-geometry
> **Comments:**
> **username_0**: Oh, im sorry. I made a mistake. The first inequality i wrote was incorect. I will edit it  
> **username_1**: It sounds like you're looking for the so-called "layers of maxima" problem.  
> **username_1**: Cross posted: http://stackoverflow.com/questions/36341739/data-structure-for-storing-points-and-finding-lower-points  
> **username_0**: 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.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-04-25. Score: 1 | Accepted answer

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

> **Comments:**
> **username_0**: 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)  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_0**: 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?  
> **username_2**: No further thought. Perhaps you could accept the answer as the literature provides a solution so this is not an 'open question' anymore :)  

---

