<p>According to <a href="http://maven.smith.edu/~orourke/TOPP/P63.html">TOPP 63</a>, 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.</p>

CC BY-SA 3.0
2011-11-16T15:42:10.970Z
2011-11-16T15:42:10.970Z
David Eppstein
<p>What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space:</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2011-11-16T05:55:33.767Z
I assume that $k$ is part of the query input, and is not a fixed constant ?
Suresh Venkat
CC BY-SA 3.0
2011-11-16T06:05:50.533Z
You assume correctly.
jbapple
CC BY-SA 3.0
2011-11-16T06:08:12.617Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-11-16T06:17:20.653Z
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")
jbapple
CC BY-SA 3.0
2011-11-16T07:28:38.133Z
It should help, and I had that in mind. But you're unlikely to get easy bounds of the form $f(n) + k$.
Suresh Venkat
<ds.data-structures><cg.comp-geom><near-neighbors>
Dynamic planar exact k-nearest neighbors for pathological data
jbapple
# Dynamic planar exact k-nearest neighbors for pathological data

(Asked by: username_0 on 2011-11-16)

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

**Tags:** ds.data-structures, cg.comp-geom, near-neighbors
> **Comments:**
> **username_1**: I assume that $k$ is part of the query input, and is not a fixed constant ?  
> **username_0**: You assume correctly.  
> **username_1**: 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.  
> **username_0**: 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")  
> **username_1**: It should help, and I had that in mind. But you're unlikely to get easy bounds of the form $f(n) + k$.  

---

## 1 answers

### Answer by username_2 on 2011-11-16. Score: 7 | Accepted answer

According to [TOPP 63](http://maven.smith.edu/~orourke/TOPP/P63.html), 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.


---

