Punkte mit maximalem Abstand zueinander finden

Neue Frage »

MichiGonomix Auf diesen Beitrag antworten »
Punkte mit maximalem Abstand zueinander finden
Meine Frage:
Hallo,

gegeben sei ein dreidimensionaler Raum, in dem 100 Punkte stochastisch verteilt sind. Man nehme zufällig einen dieser Punkte als Startpunkt P1.

Ausgehend davon sucht man einen Punkt P2 aus den 100 gegebenen Punkten, der am weitesten von P1 entfernt ist.
Nun sucht man einen Punkt P3, der einen möglichst großen und einen möglichst gleichmäßigen Abstand zu P1 und P2 hat.
Mit der gleichen Logik sucht man P4 und P5 (möglichst großer und möglichst gleichmäßiger Abstand zu allen vorhergehenden Punkten).

Wie gehe ich dabei am besten vor?

Meine Ideen:
P2 ist noch einfach, ich berechne einfach die vektoriellen Abstände aller 99 Punkte zu P1 und wähle den Punkt mit dem größten Abstand aus.

Für P3 hatte ich zuerst daran gedacht, einfach die Summe der Abstände zu P1 und P2 zu verwenden. Dadurch erhalte ich aber keine gleichmäßige Verteilung. Ein Punkt mit den Abständen 1 + 100 = 101 wäre "besser" als ein Punkt mit den Abständen 50 + 50 = 100.

Also dachte ich daran, von der Summe der Abstände die Standardabweichung aller Abstände abzuziehen und damit einen "Score" zu erstellen, der beide Kriterien (großer UND gleichmäßiger Abstand) abbildet.

Beispiel Suche nach P5:
Kandidat 1 hat folgende Abstände zu P1 bis P4: 10 | 70 | 70 | 70
Abstandssumme = 220
Sigma = 30
Score = 220 - 30 = 190

Kandidat 2 hat folgende Abstände zu P1 bis P4: 50 | 50 | 50 | 50
Abstandssumme = 200
Sigma = 0
Score = 230 - 0 = 200

Kandidat 2 würde also der bessere Punkt sein. Welches der beiden Kriterien mir wichtiger ist (max. Abstand oder möglichst gleichmäßige Verteilung) kann ich steuern, indem ich Teile oder Vielfache von Sigma von der Abstandssumme abziehe.

Prinzipiell scheint mir der Weg gangbar. Aber ich bin mir sicher, da gibt es etwas Besseres oder Eleganteres, was mir mit meinen begrenzten Mathekenntnissen unbekannt ist. Was würdet ihr vorschlagen?
HAL 9000 Auf diesen Beitrag antworten »

Denkbar wäre auch, für die Wahl von die Größe zu maximieren, und das über (Dabei meine ich mit die Ausgangsmenge der 100 Punkte.).
MichiGonomix Auf diesen Beitrag antworten »

Danke für die Antwort! also wenn ich richtig verstehe, wäre demnach der beste Kandidat der, bei dem der minimale Abstand zu allen vorhergehenden Punkten am Größten ist?
MichiGonomix Auf diesen Beitrag antworten »

Hier ein Test mit deinem Vorschlag im 3-dimensionalen Raum.
1000 Punkte mit Abstand 1 zueinander.
Erster vorgegebener Punkt (1, 1, 1).
Die danach gewählten Punkte sind kleinerwerdend rot markiert:

(darf leider keine Links posten, also bitte Leerzeichen entfernen)
ht tps: //ibb.co/k0BNf89


Gefällt mir ganz gut so, danke nochmals.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »