dist btwn points sbjct to threshold

[Rintoul, Mark Daniel]

     If you have the memory, the easiest way is probably just to
superimpose a grid over the particles, and keep track (via pointers
say) of which particles are in each grid cell.  Then, you just have
to look in your own grid cell and neighboring ones that could possibly
have a neighbor within the specified distance.  By choosing the
grid size appropriately, you can just look in your cell and the 
26 neighbor cells.  I think the simulation literature just calls
this the "cell-list" method.  It's basically just a hashing approach.


               Danny


-----Original Message-----
From: Rohit Singh
To: compgeom-discuss at research.bell-labs.com
Sent: 7/9/2001 1:18 AM
Subject: dist btwn points sbjct to threshold

Hi,
 This is a newbie question, so I don't know if this is a standard
problem:

I am doing some protein-modeling work. Given a set of points with 3-D
coordinates, I am interested in finding all pairs of points such that
the
distance between the points is less than some threshold distance. This
threshold distance is chosen, independently, on the basis of energy
considerations. For each such pair, I also need the point-point
distance.
  The brute force way I am using right now is to go through all pairs of
points and calculate their distance and see if it is less than
threshold.
Of course, one obvious improvement is to keep track, while calculating
the
inter-point distance along each dimension, of the cumulative
square-of-distance (across all the dimensions considered so far) and
stop
as soon as you exceed the square of the threshold. But since I only have
3
dimensions, it doesn't buy me much.

Are there more efficient ways of doing this?

Thanks in advance,
Rohit 


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.