8
$\begingroup$

What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space:

  • $insert(x)$
  • $delete(x)$
  • $nearest(k,x)$ (where $k$ is an integer greater than 0) returns the $k$ closest points to $x$ that are in the set.

In this particular case, I'm not particularly interested in approximate nearest neighbor, Monte Carlo algorithms, or algorithms that assume the data is well-formed in some way.

I am not as prejudiced against Las Vegas algorithms, algorithms that assume the coordinates of the point have $O(\lg n)$ bits, or algorithms with running time depending on $k$.

Improve this question
$\endgroup$
5
  • $\begingroup$ I assume that $k$ is part of the query input, and is not a fixed constant ? $\endgroup$
    – Suresh Venkat
    Commented Nov 16, 2011 at 5:55
  • $\begingroup$ You assume correctly. $\endgroup$
    – jbapple
    Commented Nov 16, 2011 at 6:05
  • $\begingroup$ that's what I was afraid of. The problem is that since k can be as much as n/2, you're really asking about middle levels of an arrangement of functions and these can change a lot on insertion and deletion. $\endgroup$
    – Suresh Venkat
    Commented Nov 16, 2011 at 6:08
  • $\begingroup$ Does it help if k is both part of the query input and a parameter of the running time? (I think this is called "output-sensitive") $\endgroup$
    – jbapple
    Commented Nov 16, 2011 at 6:17
  • $\begingroup$ It should help, and I had that in mind. But you're unlikely to get easy bounds of the form $f(n) + k$. $\endgroup$
    – Suresh Venkat
    Commented Nov 16, 2011 at 7:28

1 Answer 1

Reset to default
7
$\begingroup$

According to TOPP 63, dynamic nearest neighbors can be answered in $O($polylog$)$ time per insert, delete, or query (that is, the case $k=1$). The general case can therefore also be answered in time $O(k$ polylog$)$ per query: to do a query for $k$ points, repeatedly find and delete the nearest neighbor, then once the query is done re-insert all the points you deleted.

Improve this answer
$\endgroup$

Your Answer

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

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