Dado un conjunto finito de puntos en , ¿cómo podemos calcular eficientemente un "punto más aislado"? ?
Definimos un "punto más aislado" por
( notación aunque no sea necesariamente única. Aquí denota la distancia euclidiana). En otras palabras, estamos buscando un punto con la mayor distancia al vecino más cercano.
Un algoritmo ingenuo sería calcular todas las distancias por pares, encontrar el vecino con la menor distancia para cada punto y luego encontrar el máximo de estos. Esto requiere operaciones , pero ¿podemos hacerlo mejor que eso?
Respuestas:
Use cualquier algoritmo para todos los vecinos más cercanos ; entonces puedes resolver trivialmente tu problema. Tal algoritmo encuentra, para cada punto de datos, su vecino más cercano. El punto más aislado es aquel cuyo vecino más cercano está más alejado, por lo que una vez que haya resuelto todos los vecinos más cercanos, puede encontrar el punto más aislado mediante un escaneo lineal simple.
Aparentemente, todos los vecinos más cercanos se pueden encontrar en el tiempo ; ver las referencias en Wikipedia. O, si desea implementar algo, tome cualquier estructura de datos para los vecinos más cercanos y, para cada punto , encuentre su vecino más cercano.O(nlogn) p
fuente
Como se sugiere en los comentarios, buscaría en las consultas de vecinos más cercanos.
Hacer una consulta NN por punto debe estar en el orden de por lo que ya es mejor que la solución ingenua.O(n∗log(n))
Puede mejorarlo aún más si agrega un parámetro a la consulta NN que contiene la distancia vecina más cercana del punto más aislado que encontró hasta ahora. Luego puede abortar cualquier consulta NN tan pronto como encuentre un punto que esté más cerca que . Esto debería acelerar su búsqueda bastante.dmax dmax
Por cierto, la gente suele sugerir árboles KD para NN-Search. Los árboles KD son muy fáciles de implementar pero, en mi experiencia, escalan sistemáticamente menos bien con mayores dimensiones que otros árboles. Para o menos, recomendaría usar un R-Tree, como R * Tree (R-Star-Tree), X-Tree o STR-loaded R-Tree, o un PH-Tree (que es más como un quadtree bit a bit).d>10
fuente