# How to find the first $k$ points of high enough level using a priority search tree?

In reading Chan's paper, Closest Point Problems Simplified on a RAM, 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.

• 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 Apr 5 '13 at 2:14
• @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 Apr 5 '13 at 17:14
• @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 Apr 5 '13 at 17:19

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.