Link Cell Algorithm

The link cell algorithm comes from the domain of Molecular Dynamics Simulations. Here, for a set of molecules, pairwise interactions have to be computed under the constrain of a limited interaction range. The idea of the link cell algorithm is to divide the simulation domain into cells and sorting the molecules into the cells based on their spatial position. Traversing over interaction partners is then achieved by iterating over the molecules in the neigbouring cells instead of the entire domain. In this way the link cell algorithm reduces the original O(N^2) problem to an O(N) problem.

Related discipline(s): Molecular Dynamics