3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – jbapple
    Apr 5, 2013 at 2:14
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Joe
    Apr 5, 2013 at 17:14
  • 1
    $\begingroup$ @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. $\endgroup$
    – Joe
    Apr 5, 2013 at 17:19

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.