Durchschnittlich kleinster Abstand von Punkten berechnen

Question

Hallo :)

Ich würde gerne wissen ob es eine Rechenmethode gibt um von einer beliebigen Anzahl von zufälligen punkten, den bestimmten Punkt zu finden wo alle im Durschnitt am kürzesten entfernt find.

Hierfür hab ich ein beispiel:

Ich hab 5 Punkte A,B,C,D,E mit den Koordianten:

A: 5/7   B: 5/17   C: 21/12    D: 25/5   E: 27/4

Bei welcher Koordinate liegt der Punkt an dem der Abstand im Durchschitt am kleinsten ist und wie habt ihr gerechnet?

Wer sich darunter nicht viel vorstellen kann, dem könnte vieleicht der Wiki artikel zum Bevölkerungsmittelpunkt helfen.

Danke für die Antworten :)

Answer 1

Zentralpunkt
( x | y )

Abstand eines Punkts zum Zentralpunkt

√ [ ( x -  x1 )^2 + ( y - y1 )^2 ]

Insgesamter Abstand
f ( x,y ) = abstand1 + abstand2 ... abstand5
f ( x,y ) =  √ [ ( x -  x1 )^2 + ( y - y1 )^2 ] +...
                √ [ ( x -  x5 )^2 + ( y - y5 )^2 ]

Davon die 1.Ableitung nach x und y bilden,
zu Nullsetzen und den Extrempunkt bestimmen.

Jetzt ergab sich die Frage ob die Wurzel wegen
besserer Berechenbarkeit weggelassen werden kann.

Hier meine Überlegungen zunächst an einem
einfachen Beispiel

term und √ term ( 1 und 2 ) haben denselben Extrempunkt.
term ´= 0

( Darunter das kann überlesen werden )

Daselbe wurde für eine Funktion mit
( t1 + t2 ) bzw. ( √ t1 + √ t2 ) durchgeführt.

Falls ( t1 ´ = 0 ) und ( t2 ´  = 0 ) ist bei beiden ein Extremwert
gegeben.

Die Wurzel kann also weggelassen werden

f ( x,y ) =  (  ( x -  x1 )^2 + ( y - y1 )^2 ) +...
                ( ( x -  x5 )^2 + ( y - y5 )^2 )

Geht noch weiter.

Comments

f ( x,y ) = Summe der
" reduzierten Abstände ohne Wurzel "



Bei einer partiellen Ableitung nach x entfallen
die y-Terme

10 * x -166 = 0
x = 16.6

Ableitung nach y

10 * y - 90 = 0
y = 9

Zentralpunkt
( 16.6 | 9 )

Dasselbe Ergebnis kann durch Bildung
des Mittelwerts der x-Koordinaten und
y-Koordinaten erzielt werden.

Soweit meine Überlegungen.

---

So weit war ich auch. Das Betrachten des quadratischen Abstandes unterscheidet sich aber doch von dem gewurzelten Abstand. Mein Solvermodell unter Excel ermittelt für den quadratischen Abstand die über die Ableitung gefundene LÖsung und für den gewurzelten Abstand die im Kommentar unten genannte Lösung....

---

Hier noch

Daselbe wurde für eine Funktion mit
( t1 + t2 ) bzw. ( √ t1 + √ t2 ) durchgeführt.

Falls ( t1 ´ = 0 ) und ( t2 ´  = 0 ) ist bei beiden ein Extremwert
gegeben.

In die Original-Abstandsfunktion eingesetzt
x:=16.6
y:=9
A = 52.03

x:=20.06
y:=9.25
A = 50.29

Deine Lösung ist also besser.
Jetzt muß ich einmal schauen wo bei mir der Fehler ist.

---

Ich seh keinen Fehler - ich hab analytisch und mit dem Solver die gleiche Lösung gefunden wie Du auch. Ich denke es liegt daran, das quadrieren keine Äquivalenzumformung ist und damit Lösungen verloren gehen? Jedenfalls bei mehr als 2 Punkten - bei zwei Punkten sind beide Lösungen identisch - was jetzt nicht wirklich überraschend ist :-), oder?

---

Es hat nichts damit zu tun, dass Quadrieren keine Aequivalenzumformung ist. Da kommt schlicht deshalb was anderes raus, weil Minimieren der Abstandssumme und Minimieren der Summe der Abstandsquadrate verschiedene Probleme mit im allgemeinen verschiedenen Lösungen sind.

Wie man der Literatur entnehmen kann, ist das erste Problem ohne Numerik nur mit Papier und Bleistift nicht loesbar. Siehe ausser dem schon angegebenen Link auch https://en.wikipedia.org/wiki/Geometric_median oder gleich https://www.google.de/search?q=geometric+median.

Answer 2

Schreibe \(X=(x,y)\) und minimiere \(f(x,y)=\overline{AX}+\cdots+\overline{EX}\). Das rechnet sich aber schlecht.

Hier hat jemand was ganz interessantes darueber geschrieben: http://www.math.uni-hamburg.de/home/eckhardt/Standort.pdf

Alternativ kannst Du die Summe der Abstandsquadrate \(g(x,y)=\overline{AX}^2+\cdots+\overline{EX}^2\) minimieren. Das rechnet sich sehr leicht und raus kommt der Schwerpunkt. Ist aber nicht der gesuchte Punkt.

Comments

Rechnet sich schlecht - der ist gut :-).

Ich hab einfach mal den Solver in XL darauf angesetzt und den Punkt (20.0617649,9.25162291) erhalten....

---

-------------------------------------------