I want to introduce two algorithms, useful for fast collision detection in granular medium simulations. We all know that the most time consuming part in molecular dynamics simulations is the collision detection. Usually, this problem can be solved by restricting the shape of the particles to spheres. But if you want to use arbitrary convex polygons you need faster algorithms.
At first, a little bit of philosophy: Generally, in computational physics we want information, and you have to pay for it with computing time. So if information is expensive, you should recycle it!
Seriously, if we have a molecular dynamics simulation of granular materials, the state of the system is changing very slowly. So the information, we gained in the last time step is nearly correct. We should try to reuse this information. Either by using it as starting conditions or by calculating only the changes between the time-steps, so we can correct the old information. If we choose good algorithm doing this work, we can save a lot of time.