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$.

  • $\begingroup$ I assume that $k$ is part of the query input, and is not a fixed constant ? $\endgroup$ – Suresh Venkat Nov 16 '11 at 5:55
  • $\begingroup$ You assume correctly. $\endgroup$ – jbapple Nov 16 '11 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 Nov 16 '11 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 Nov 16 '11 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 Nov 16 '11 at 7:28

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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