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.
How to find the first $k$ points of high enough level using a priority search tree?
ds.data structures;cg.comp geom
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