Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!pasteur!ucbvax!ucsfcgl!cgl.ucsf.edu!seibel
From: seibel@cgl.ucsf.edu (George Seibel%Kollman)
Newsgroups: comp.graphics
Subject: Re: A simple 2-D particle system (animated atoms)
Message-ID: <10789@cgl.ucsf.EDU>
Date: 7 Apr 88 06:54:19 GMT
References: <231@abvax.UUCP>
Sender: daemon@cgl.ucsf.edu
Reply-To: seibel@socrates.ucsf.edu.UUCP (George Seibel%Kollman)
Distribution: na
Organization: UCSF Computer Graphics Lab
Lines: 15
Keywords: animated, computational speedups O(n*n)

Regarding the generation of neighbor lists in particle simulations,
and avoiding O(N**2) complexity, this is quite the big deal among
computational physicists and chemists.  Here are a couple of refs:

Grid-cell technique and some good info on periodic boundary conditions:
W.F. van Gunsteren, et. al., "On Searching Neighbors in Computer 
Simulations of Macromolecular Systems", J. Comp. Chem. Vol 5, 272-279 (1984).

A very interesting O(N) neighbor list method:
Jay Boris, "A Vectorized 'Near Neighbors' Algorithm of Order N
Using a Monotonic Logical Grid", J. Comp. Phys, vol ? 1-20, (1986).

If anyone implements the Boris algorithm, let me know.

George Seibel, UCSF
seibel@cgl.ucsf.edu