dist btwn points sbjct to threshold

[Paul Heckbert]

The algorithm you describe takes O(n^2) time, where n is the number of
points, and that is of course the best you can do for arbitrary point sets,
since the output set could be that large, but when you have fairly well
distributed points, as you probably do for protein work, you should be able
to get O(n) performance in practice.

A simple algorithm I've used for related problems is to create a k*k*k grid
of cubes, each of which contains a list of points within it.  You could
choose k such that your cube size is proportional to the threshold distance
you're interested in, or if your points are uniformly distributed through
space (probably not true for proteins) you could try k proportional to n^.33
.  Using that simple data structure, it is a simple matter of checking a
cube and perhaps some of the neighboring cubes to find all points within a
given distance of some query point.  If your points are well-distributed and
you've chosen k appropriately, the average work required for each query will
be O(1), so finding all pairs with distance below threshold will be O(n).

See the paper "Fast Surface Particle Repulsion" at http://www.cs.cmu.edu/~ph
for more details on the cubical bucketing scheme.

Paul Heckbert
Computer Science Dept
Carnegie Mellon University

> -----Original Message-----
> From: Rohit Singh [mailto:rohitsi at CS.Stanford.EDU]
> Sent: Monday, July 09, 2001 3:18 AM
> To: compgeom-discuss at research.bell-labs.com
> Subject: dist btwn points sbjct to threshold
>
> 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?


-------------
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.