La pregunta puede leerse de varias maneras. Yo la interpreto como que tienes un gran número de puntos y pretendes sondearlos repetidamente con puntos arbitrarios, dados como pares de coordenadas, y deseas obtener los n puntos más cercanos al sondeo, con n fijado de antemano. (En principio, si n va a variar, se podría establecer una estructura de datos para cada posible n y seleccionarlo en tiempo O(1) con cada sonda: esto podría llevar un tiempo de configuración muy largo y requerir mucha RAM, pero se nos dice que ignoremos tales preocupaciones).
Construir el diagrama de Voronoi de orden n de todos los puntos. Esto divide el plano en regiones conectadas, cada una de las cuales tiene los mismos n vecinos. Esto reduce la situación al problema de punto en polígono, que tiene muchas soluciones eficientes.
Utilizando una estructura de datos vectorial para el diagrama de Voronoi, las búsquedas de puntos en polígonos tardarán O(log(n)). A efectos prácticos, se puede hacer O(1) con un coeficiente implícito extremadamente pequeño simplemente creando una versión raster del diagrama. Los valores de las celdas del raster son: (i) un puntero a una lista de los n puntos más cercanos o (ii) una indicación de que esta celda se encuentra a caballo entre dos o más regiones del diagrama. La prueba para un punto arbitrario en (x,y) se convierte en
Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).
Para conseguir un rendimiento O(1), la malla rasterizada tiene que ser lo suficientemente fina como para que relativamente pocos puntos de la sonda caigan en celdas que atraviesen múltiples regiones de Voronoi. Esto siempre puede lograrse, con un gasto potencialmente grande en el almacenamiento de las mallas.
