dist btwn points sbjct to threshold

[David Eppstein]

On 7/9/01 12:18 AM -0700, Rohit Singh wrote:
> 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 can be solved in time O(n log n + k) where k is the number of output 
points.  I think the first paper to do this may be Bentley, Stanat, and 
Williams, "The complexity of finding fixed radius near neighbors", Inf. 
Proc. Lett. 6:209-213, 1977.  Another algorithm is included in my paper 
with Dickerson, "Algorithms for proximity problems in higher dimensions",
Comp. Geom. Th. & Appl. 5:277-291, 1996, 
http://www.ics.uci.edu/~eppstein/pubs/DicEpp-CGTA-96.pdf

I don't know about the practicality or available implementations of these 
algorithms, though.
-- 
David Eppstein       UC Irvine Dept. of Information & Computer Science
eppstein at ics.uci.edu http://www.ics.uci.edu/~eppstein/


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