Der zeitaufwändigste Teil bei Molekulardynamik-Simulationen ist die Kollisionserkennung. Normalerweise wird dieses Problem gelöst, indem die Form der Partikel auf Kugeln beschränkt wird. Ich werde einen Algorithmus vorstellen, der ursprünglich von D. Baraff und M. C. Lin für Virtual-Reality-Visualisierungen entwickelt wurde und der es uns ermöglicht, komplexe Polyeder (bis zu 920 Flächen und mehr) zu verwenden. Die erwartete Laufzeit ist O(N), wobei N die Anzahl der Partikel in der Simulation ist. Weder die Komplexität noch die Form der Partikel haben einen Einfluss auf die Laufzeit.
Wie kann dies erreicht werden, wenn die optimale Laufzeit nicht kleiner als O(N log N+k) sein kann? Das auffälligste Merkmal des Algorithmus ist die Wiederverwendung der im letzten Zeitschritt berechneten Informationen. Der Algorithmus besteht aus zwei Teilen.
Im ersten Schritt sucht er nach Kollisionen der Bounding Boxes der Teilchen. Sie werden erkannt, indem die Liste aller Boxen umsortiert wird. Insertion-sort erlaubt hier eine Sortierung in O(N)-Operationen. Der zweite Schritt ist eine schnelle Methode zur Berechnung des Abstands zwischen zwei Polyedern, indem die nächstgelegenen Punkte gefunden und verfolgt werden. In MD-Simulationen ist dieser Algorithmus so effizient, dass die benötigte CPU-Zeit unabhängig von der Partikelform ist.