Zitat:
Wenn ein Objekt sich bewegt, dann müssen nur 2*N-1 Entfernungen neu berechnet werden,
Warum das? Es gibt doch nur (N-1) andere Objekte zu denen sich die Entfernung ändert.
Ein anderer Ansatz ist ein Teile und Herrsche, den ich mal für den BWINF erdacht habe:
Teile dein Gebiet in denen die Körper sind, in Sektoren ein und gib dann jedem Sektor eine Liste mit den enthaltenen Körpern. Bei jedem Zeitschritt werden dann diese Listen erneuert, was proportional zu N ist.
Wenn du für einen Körper dann die nächsten Körper suchst, betrachtest du erst die anderen Körper im Sektor. Wenn der minimale Abstand zu denen kleiner ist, als der Abstand deines Körpers zu einer Sektorgrenze, bist du fertig, alternativ musst du noch die Elemente in diesem Sektor prüfen. Je nach Sektorengröße bist du damit auf jeden Fall schneller als ein BruteForce ansatz.