When all of the item pairs should be looped over (e.g. pair potential among atoms), the order of computational complexity is N2 . However, if a cutoff of distance presents so that two items with distance larger than a certain distance are unrelated (e.g. no interaction between two atoms), cell index method can be used to reduce the complexity down to N.
The core idea of cell index method is to divide the space into cells with side length a little larger than cutoff and loop only for those item pairs in the same cell or neighbored cells. Details can be found in M. P. Allen and D. J. Tildesley, Computer Simulation of liquids.
C++ object implemented in cell.h and cell.C with support of vector.h have actually been used in most of the algorithms introduced on this website, such as bond order parameters and local curvature fitting.
Back to Algorithms page