# Dynamic planar exact k-nearest neighbors for pathological data

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

• I assume that $k$ is part of the query input, and is not a fixed constant ? Nov 16, 2011 at 5:55
• You assume correctly. Nov 16, 2011 at 6:05
• 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. Nov 16, 2011 at 6:08
• 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") Nov 16, 2011 at 6:17
• It should help, and I had that in mind. But you're unlikely to get easy bounds of the form $f(n) + k$. Nov 16, 2011 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.