Encontrar el punto que suma de distancias al conjunto de otros puntos es mínimo

Question

Tengo un conjunto (X) de puntos (no muy grandes, digamos 1-20 puntos) y el segundo (Y), un conjunto de puntos mucho más grande. Necesito elegir un punto de Y cuya suma de distancias a todos los puntos de X son mínimos.

Se me ocurrió una idea de que trataría a X como un vértice de un polígono y encontraría el centroide de este polígono, y luego elegiré un punto de Y más cercano al centroide. Pero no estoy seguro de si centroide minimiza la suma de sus distancias a los vértices del polígono, entonces no estoy seguro de si esta es una buena forma. ¿Hay algún algoritmo para resolver este problema?

Los puntos se definen por coordenadas geográficas.

Answer 1

El centro del polígono podría no ser el correcto, pero existe tal punto.

En el documento: n-ellipses and the minimum distance problem, se muestra que si los puntos (llamados focos, el conjunto de X) no están alineados entonces

• Hay un punto único (denominado centro) para el que la suma de distancias se reducen al mínimo. ¡Este punto es tal que la suma de los vectores unitarios desde ese punto hasta los focos es cero!

• El lugar geométrico de puntos para los que la suma de las distancias es constante es una curva convexa (llamado un n-elipse) que contiene el centro

• El n-elipse para la distancia D contiene completamente el n-elipse para cualquier otra distancia D 'para el que D' < D.

de este modo se puede hacer algún tipo de algoritmo de subida de pendientes para encontrar el centro.

Por supuesto, estas n-elipses no son necesariamente círculos, por lo que simplemente elegir el punto más cercano al centro podría no funcionar, pero podría ser una buena aproximación.

Tal vez pueda hacer un preprocesamiento en los 20 puntos (si son fijos) para descubrir un buen esquema de particionamiento (basado en la información anterior).

Espero que ayude.

Answer 2

Si desea reducir al mínimo la suma de los cuadrados de las distancias (no la suma de las distancias), entonces el punto que minimiza la suma que es el promedio de los puntos en X.

Prueba:

sum(squares of distances) = (x-x0)^2 + (y-y0)^2 + (x-x1)^2 + (y-y1)^2 + ... 

d/dx sum(squares of distances) = 2(x-x0) + 2(x-x1) + ... = 2(Nx - x0 - x1 - ...) 

la suma se reduce al mínimo cuando la derivada es cero, lo que ocurre cuando Nx = x0+x1+..., por lo x = (x0+x1+...)/N

el derivado es simétrica en torno a este punto, y la función es cuadrática, así que estoy seguro de que el poin más cercano t en Y a este punto promedio es lo mejor.

Minimizar las distancias es más difícil, pero sospecho que el mismo algoritmo, con más libertad de acción en el conjunto de Ys ​​que pruebe, también funcionaría.

Answer 3

Como quiera la suma mínima de distancias, creo que puede reducir el conjunto de puntos X a su media espacial. Luego puede usar un KDTree o algún tipo de árbol de particiones espaciales para encontrar el punto en Y más cercano a la media espacial de X. Usar un árbol de particiones espaciales puede ahorrar un buen trabajo en comparación con el control de todos los puntos posibles.

Answer 4

Disculpe por sugerir la fuerza bruta. La forma en que se plantea la pregunta no sabemos dónde se encuentran X, Y. Supongamos que X tiene 30 puntos, Y es 1000 puntos. Luego, para cada punto de Y suma 30 distancias. En total 30000 cálculos, hechos en un santiamén. Esto garantiza un mínimo. Encontrar un "centro" de X y elegir la Y más cercana será solo una solución aproximada.

La pregunta más interesante es encontrar un punto para X solo. ignore Y. Para X tres puntos solamente, el punto de Fermat-Torichelli resuelve el problema.