Finde den Punkt, an dem die Summe der Abstände zu anderen Punkten minimal ist

Question

Ich habe eine Menge (X) Punkte (nicht sehr groß, sagen wir 1-20 Punkte) und die zweite (Y), viel größere Menge an Punkten. Ich muss einen Punkt von Y wählen, der die Summe der Abstände zu Punkte von X ist minimal.

Ich kam auf eine Idee, dass ich X als Eckpunkte eines Polygons behandeln und Zentroid dieses Polygons finden würde, und dann werde ich einen Punkt von Y am nächsten zum Schwerpunkt wählen. Aber ich bin mir nicht sicher, ob der Zentroid die Summe seiner Abstände zu den Eckpunkten des Polygons minimiert, also bin ich mir nicht sicher, ob das ein guter Weg ist? Gibt es einen Algorithmus zur Lösung dieses Problems?

Punkte werden durch geografische Koordinaten definiert.

Answer 1

Schwerpunkt des Polygons möglicherweise nicht richtig, aber ein solcher Punkt existiert.

In dem Papier: n-ellipses and the minimum distance problem ist es, wenn die Punkte (so genannte Brennpunkte, Ihr Satz von X) nicht kollinear dann

• Es ist ein einzigartiger Punkt (genannt Mitte), für die die Summe gezeigt, dass von Entfernungen sind minimiert. Dieser Punkt ist so, dass die Summe der Einheitsvektoren von diesem Punkt zu den Brennpunkten Null ist!

• Der Ort der Punkte, für die die Summe der Abstände konstant ist eine konvexe Kurve ist, die das Zentrum

• Die n-Ellipse für die Entfernung D vollständig enthält die n-Ellipse (eine n-Ellipse bezeichnet) für anderer Abstand D ‚für die D‘ < D.

So können Sie irgendeine Art von hill-climbing-Algorithmus tun, das Zentrum zu finden.

Natürlich sind diese N-Ellipsen nicht unbedingt Kreise, daher kann es nicht funktionieren, nur den Punkt auszuwählen, der dem Mittelpunkt am nächsten ist, aber es könnte eine gute Annäherung sein.

Sie können vielleicht auf den 20 Punkten eine Vorverarbeitung tun (wenn diese festgelegt sind) ein gutes Partitionierungsschema, um herauszufinden, (basierend auf den oben genannten Informationen).

Hoffe, dass hilft.

Answer 2

Wenn Sie die Summe der Quadrate der Abstände (nicht die Summe der Abstände), dann ist der Punkt zu minimieren, die diese Summe minimiert, ist der Mittelwert der Punkte in X.

Beweis:

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 - ...) 

die Summe minimiert wird, wenn die Ableitung Null ist, was Nx = x0+x1+... tritt auf, wenn, so x = (x0+x1+...)/N

das Derivat ist symmetrisch um diesen Punkt, und die Funktion ist quadratisch, also bin ich ziemlich sicher, dass in der Nähe poin t in Y zu diesem Durchschnittspunkt ist der beste.

Die Entfernung zu minimieren ist schwieriger, aber ich vermute, dass der gleiche Algorithmus mit mehr Spielraum in der Ys, die Sie testen, auch funktionieren würde.

Answer 3

Da Sie die minimale Summe der Entfernungen wollen, glaube ich, dass Sie die Menge der Punkte X auf ihren räumlichen Mittelwert reduzieren können. Dann können Sie einen KDTree- oder einen räumlichen Partitionierungsbaum verwenden, um den Punkt in Y zu finden, der dem räumlichen Mittelwert von X am nächsten liegt. Die Verwendung eines räumlichen Partitionierungsbaums kann im Vergleich zur Prüfung aller möglichen Punkte viel Arbeit einsparen.

Answer 4

Entschuldigung für Brute-Force-hindeutet. Wie die Frage gestellt wird, wissen wir nicht, wo X, Y liegen. Angenommen X ist 30 Punkte, Y ist 1000 Punkte. Dann für jeden Punkt von Y Summe 30 Entfernungen. Insgesamt 30000 Berechnungen, im Handumdrehen erledigt. Dies garantiert ein Minimum. Das Finden eines "Zentrums" von X und das Auswählen des nächsten Y wird nur eine ungefähre Lösung sein.

Die interessantere Frage ist allein einen solchen Punkt für X zu finden. Ignoriere Y. Für X nur drei Punkte löst der Fermat-Torichelli-Punkt das Problem.