Encontrar los tres puntos más cercanos a cada punto en un plano 2D

Question

Se le proporciona una lista de puntos en el plano, escriba un programa que emite cada punto junto con los otros tres puntos más cercanos . Estos tres puntos ordenados por distancia.

Por ejemplo, dado un conjunto de puntos en los que cada línea es de la forma: ID coordenada x y la coordenada

1 0.0 0.0 
2 10.1 -10.1 
3 -12.2 12.2 
4 38.3 38.3 
5 79.99 179.99 

su programa debe salida:

1 2,3,4 
2 1,3,4 
3 1,2,4 
4 1,2,3 
5 4,3,1 

Esta es una pregunta de la entrevista que encontré en un foro en línea. Puedo pensar en una solución O (n * n): calcule la distancia de cada punto a cada otro punto. Devuelve los puntos de distancia mínima para este punto. Repita el proceso para los otros puntos

Answer 1

Es posible que desee examinar las estructuras de datos espaciales como el árbol k-d o el árbol cuádruple, que brindan excelentes garantías de tiempo esperado para las búsquedas de vecinos más cercanos. Por ejemplo, el árbol k-d puede realizar búsquedas de vecinos más cercanas en el tiempo de O (n) del peor caso y el tiempo esperado de O (sqrt N) después de realizar el trabajo de preprocesamiento de O (n log n).

Alternativamente, si sabe que los puntos se distribuyen aleatoriamente en su mayoría, podría considerar el espacio de partición en una colección de cubos de tamaño fijo. Para encontrar los vecinos más cercanos a un punto, puedes ver todos los puntos en el mismo cubo, luego todos los puntos en cubos cercanos, etc. Esto debería estar cerca de O (n/b) tiempo por punto si los puntos están bien distribuido y hay b cubos.

Espero que esto ayude!

Answer 2

Lo que están buscando es si alguna vez oído hablar de la Delaunay triangulation, que a su vez conduce a un O (n registro n) algoritmo.

Editar. No es tan simple como insinué, según la corrección en los comentarios. Una puede utilizar la triangulación de Delaunay para encontrar los tres vecinos más cercanos en O (n registro n) tiempo, pero requiere un poco de trabajo, como se explica en el artículo de Dickerson, Drysdale y Sack, "Simple Algorithms for Enumerating Interpoint Distances and Finding k Nearest Neighbors."