The most time consuming part in molecular dynamics simulations is the collision detection. Usually, this problem is solved by restricting theshape of the particles to spheres. I will present an algorithm, originally developed for virtual reality visualizations by D.Baraff and M.C.Lin, that enables us to use complex polyhedra (up to 920 faces and more). The expected run time is O(N), where N is the number of particles in the simulation. Neither complexity nor shape of the particles affect the run time.
How can this be achieved, if the optimal run time can't besmaller than O(N log N+k)? The most striking feature of the algorithm is its reuseing information calculated in the last time step.
The algorithm consists of two parts. In the first step, it looks for collisions of the particles' bounding boxes. They are detectedresorting the list of all boxes. Insertion-sort allows sorting in O(N) operations here. The second step is a fast method to compute the distance between two polyhedra by finding and tracking the closest points. In MD simulations, this algorithms is so efficient that the amount of required CPU time is independent of the particle shape.