Dinámicos planos vecinos k-cercanos más exactos para datos patológicos

¿Cuáles son los resultados más conocidos para una estructura de datos que ofrece las siguientes operaciones en conjuntos de puntos en el espacio euclidiano bidimensional:

• $insert(x)$
• $delete(x)$
• (donde k es un número entero mayor que 0) devuelve los k puntos más cercanos a x que están en el conjunto.$nearest(k,x)$$k$$k$$x$

En este caso particular, no estoy particularmente interesado en el vecino más cercano, los algoritmos de Monte Carlo o los algoritmos que suponen que los datos están bien formados de alguna manera.

No tengo prejuicios contra los algoritmos de Las Vegas, los algoritmos que suponen que las coordenadas del punto tienen bits , o los algoritmos con tiempo de ejecución dependiendo de k .$O(\lg n)$$k$

$O($$)$$k=1$$O(k$$)$$k$