<p>The tree is binary and has depth $O(\log(n))$ and the properties that:</p>

<ul>
<li><p>for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent.</p></li>
<li><p>for any node $v$, all descendants in the left subtree have x-coordinate smaller than $v$, and all descendants in the right subtree have x-coordinate larger than $v$.</p></li>
</ul>

<p>This means that your solution set from which you choose $k$ elements is actually <del>a subtree</del> one side (in the left/right sense) of what remains when a path is deleted, and can be traversed with DFS in $(\log(n)+k)$ time.  Note that the priority search tree may require dummy points at which you root subtrees to keep the depth low.</p>

<p>This paper may give some clarification: <a href="http://people.scs.carleton.ca/~michiel/MinMaxPST.pdf" rel="nofollow">http://people.scs.carleton.ca/~michiel/MinMaxPST.pdf</a></p>

CC BY-SA 3.0
2013-04-06T20:46:36.337Z
2013-04-07T00:55:42.513Z
2013-04-07T00:55:42.513Z
Andrew D. King
<p>In reading Chan's paper,
<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3912" rel="nofollow">Closest Point Problems Simplified on a RAM</a>,
the following came up as a sub-problem:</p>

<p><strong>Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (ordered by $x$-coordinate) which dominate $q$.</strong></p>

<p>Chan asserts that this query can be answered in $O(\log n + k)$ time using a priority search tree, but doesn't give details, and the details are not clear to me. The traditional query for a priority search tree is a 3-sided range query, but this query is different because we are given a 2-sided range (an upper-right quadrant) and a maximum number of points to report. We should report the $k$ "leftmost" points in the 2-sided range.</p>

CC BY-SA 3.0
2013-04-05T02:14:06.157Z
I don't really understand the question. What are the "first" $k$ points, and what does it mean to "dominate" a point? Are those both by the same axis? If you have a balanced binary search tree that answers queries like "Which $k$ keys are the smallest ones larger than the key $x$?" in time $O(\lg n + k)$, will that answer your question?
jbapple
CC BY-SA 3.0
2013-04-05T17:14:41.203Z
@jbapple a point $p$ *dominates* $q$ if both coordinates are at least as large as $q$, i.e. $p.x \geq q.x$ and $p.y \geq q.y$.
Joe
CC BY-SA 3.0
2013-04-05T17:19:13.440Z
@jbapple here's a naiive algorithm that clarifies the points which should be returned. Sort all the points according to $x$ coordinate. Store them in a linked list. Given a pointer to the location of $q$ in the linked list, we simply walk through the list. First look at its successor $p_1$ in the linked list, the next point ordered by $x$ coordinate. However, $p_1$ only "counts" if its $y$ coordinate is at least as high as $q.y$. Then, we look at the successor of $p_1$, and again compare $p_1.y$ and $q.y$. We continue until we have found $k$ points that count.
Joe
<ds.data-structures><cg.comp-geom>
How to find the first $k$ points of high enough level using a priority search tree?
Joe
# How to find the first $k$ points of high enough level using a priority search tree?

(Asked by: username_0 on 2013-04-04)

In reading Chan's paper,
[Closest Point Problems Simplified on a RAM](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3912),
the following came up as a sub-problem:

**Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points (ordered by $x$-coordinate) which dominate $q$.**

Chan asserts that this query can be answered in $O(\log n + k)$ time using a priority search tree, but doesn't give details, and the details are not clear to me. The traditional query for a priority search tree is a 3-sided range query, but this query is different because we are given a 2-sided range (an upper-right quadrant) and a maximum number of points to report. We should report the $k$ "leftmost" points in the 2-sided range.

**Tags:** ds.data-structures, cg.comp-geom

> **Comments:**
> **username_1**: I don't really understand the question. What are the "first" $k$ points, and what does it mean to "dominate" a point? Are those both by the same axis? If you have a balanced binary search tree that answers queries like "Which $k$ keys are the smallest ones larger than the key $x$?" in time $O(\lg n + k)$, will that answer your question?  
> **username_0**: @username_1 a point $p$ *dominates* $q$ if both coordinates are at least as large as $q$, i.e. $p.x \geq q.x$ and $p.y \geq q.y$.  
> **username_0**: @username_1 here's a naiive algorithm that clarifies the points which should be returned. Sort all the points according to $x$ coordinate. Store them in a linked list. Given a pointer to the location of $q$ in the linked list, we simply walk through the list. First look at its successor $p_1$ in the linked list, the next point ordered by $x$ coordinate. However, $p_1$ only "counts" if its $y$ coordinate is at least as high as $q.y$. Then, we look at the successor of $p_1$, and again compare $p_1.y$ and $q.y$. We continue until we have found $k$ points that count.  

---

## 1 answers

### Answer by username_2 on 2013-04-06. Score: 5 | Accepted answer

The tree is binary and has depth $O(\log(n))$ and the properties that:

* for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent.
* for any node $v$, all descendants in the left subtree have x-coordinate smaller than $v$, and all descendants in the right subtree have x-coordinate larger than $v$.

This means that your solution set from which you choose $k$ elements is actually ~~a subtree~~ one side (in the left/right sense) of what remains when a path is deleted, and can be traversed with DFS in $(\log(n)+k)$ time. Note that the priority search tree may require dummy points at which you root subtrees to keep the depth low.

This paper may give some clarification: <http://people.scs.carleton.ca/~michiel/MinMaxPST.pdf>


---

