dist btwn points sbjct to threshold

Rohit Singh rohitsi at CS.Stanford.EDU
Mon Jul 9 01:18:06 PDT 2001

 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,

The compgeom mailing lists: see
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.

More information about the Compgeom-announce mailing list