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