## Cell Index Method

When all of the item pairs should be looped over
(e.g. pair potential among atoms), the order of computational
complexity is *N*^{2} . 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

*
*