Encontrar el punto más alejado en un conjunto de otro conjunto

Question

Mi objetivo es una implementación más eficiente del algoritmo presentado in this question.

considerar dos conjuntos de puntos (en N-espacio. 3-espacio para el caso del ejemplo de RGB espacio de color, mientras que una solución para 1-espacio 2-espacio difiere sólo en el cálculo de la distancia). ¿Cómo se encuentra el punto en el primer conjunto que está más alejado de su vecino más cercano en el segundo conjunto?

En un ejemplo de 1 espacio, dados los conjuntos A: {2,4,6,8} y B: {1,3,5}, la respuesta sería 8, ya que 8 está a 3 unidades de distancia de 5 (su vecino más cercano en B) mientras que todos los demás miembros de A están a solo 1 unidad de distancia de su vecino más cercano en B. edición: 1 espacio es demasiado simplificado, ya que la clasificación está relacionada con la distancia de una manera que no dimensiones.

La solución en la pregunta fuente implica una comparación de fuerza bruta de cada punto en un conjunto (todos R, G, B donde 512> = R + G + B> = 256 y R% 4 = 0 y G% 4 = 0 y B% 4 = 0) a cada punto en el otro conjunto (tabla de colores). Ignore, por el bien de esta pregunta, que el primer conjunto se elabora programáticamente en lugar de repetirse como una lista almacenada como el segundo conjunto.

Answer 1

Primero debe encontrar el vecino más cercano de cada elemento en el otro conjunto.

Para hacer esto de manera eficiente necesita un algoritmo nearest neighbor. Personalmente implementaría un kd-tree solo porque lo hice en el pasado en mi clase de algoritmo y fue bastante sencillo. Otra alternativa viable es un R-tree.

Haga esto una vez para cada elemento en el conjunto más pequeño. (Agregue un elemento del más pequeño al más grande y ejecute el algoritmo para encontrar el vecino más cercano.)

De esto, debería poder obtener una lista de los vecinos más cercanos para cada elemento.

Mientras busca los pares de vecinos más cercanos, guárdelos en una estructura de datos clasificados que tenga un método de adición rápida y un método getMax rápido, como heap, ordenado por Euclidean distance.

Luego, una vez que haya terminado, pregunte al montón por el máximo.

El tiempo de ejecución para este descompone como sigue:

N = tamaño del conjunto más pequeño
M = tamaño del conjunto más amplio

• N * O (log M + 1) para todos el vecino más cercano de kd chequea.
• N * O (1) para calcular la distancia euclidiana antes de agregarla al montón.
• N * O (log N) para agregar los pares en el montón.
• O (1) para obtener la respuesta final: D

Así que al final todo el algoritmo es O (N * log M).

Si no le importa el orden de cada par, puede ahorrar un poco de tiempo y espacio manteniendo solo el máximo encontrado hasta ahora.

* Descargo de responsabilidad: Todo esto supone que no utilizará un número enormemente alto de dimensiones y que sus elementos siguen una distribución casi aleatoria.

Answer 2

EDIT: Quise decir nlog (n) donde n es la suma de los tamaños de ambos conjuntos.

En el conjunto 1-espacio que se podría hacer algo como esto (pseudocódigo)

utilizar una estructura como esta = 0
(2) Lea todo

Struct Item { 
    int value 
    int setid 
} 

(1) Distancia máxima los conjuntos en las estructuras del artículo
(3) crear una matriz de punteros a todos los artículos
(4) Clasificar la matriz de punteros por Item-> campo de valor de la estructura
(5) a pie de la matriz a partir de principio a fin, comprobando si el Item-> setid es diferente de la anterior Item-> SETID si (SetIDs son diferentes)
verificación si esta distancia es mayor que Max Distancia de ser así establecer MaxDistance a esta distancia

Retorno la distancia máxima.

Answer 3

El enfoque más obvio parece ser el de crear una estructura de árbol en un conjunto para permitirle buscar con relativa rapidez. Un kd-tree o similar probablemente sea apropiado para eso.

Una vez hecho esto, recorre todos los puntos en el otro conjunto y utiliza el árbol para encontrar su vecino más cercano en el primer conjunto, manteniendo un registro del máximo sobre la marcha.

Es nlog (n) para construir el árbol, y el registro (n) para una búsqueda por lo que todo debe ejecutarse en nlog (n).

Answer 4

Para hacer las cosas más eficientes, considere usar un algoritmo de Pigeonhole: agrupe los puntos en su conjunto de referencia (su tabla de colores) por su ubicación en n-espacio. Esto le permite buscar de manera eficiente al vecino más cercano sin tener que repetir todos los puntos.

Por ejemplo, si trabajaba en 2 espacios, divida su plano en una cuadrícula de 5 x 5, dando 25 cuadrados, con 25 grupos de puntos.

En 3 espacios, divide tu cubo en una cuadrícula de 5 x 5 x 5, dando 125 cubos, cada uno con un conjunto de puntos.

Luego, para probar el punto n, encuentre el cuadrado/cubo/grupo que contiene ny la distancia de prueba a esos puntos. Solo necesita probar puntos de grupos vecinos si el punto n está más cerca del borde que al vecino más cercano del grupo.

Answer 5

Para cada punto de la serie B, encontrar la distancia a su vecino más cercano en el conjunto A.

Para encontrar la distancia a cada vecino más cercano, se puede utilizar un kd-tree, siempre y cuando el número de dimensiones es razonable, no hay demasiados puntos, y usted hará muchas consultas; de lo contrario, sería demasiado costoso construir el árbol para que valga la pena.

Answer 6

Tal vez estoy malinterpretando la pregunta, pero ¿no sería más fácil simplemente invertir el signo de todas las coordenadas en un conjunto de datos (es decir, multiplicar un conjunto de coordenadas por -1) y luego buscar el primer vecino más cercano (¿Cuál sería el vecino más lejano)? Puede usar su algoritmo knn favorito con k = 1.