dist btwn points sbjct to threshold

David Eppstein eppstein at ics.uci.edu
Wed Jul 11 16:48:36 PDT 2001

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, 

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