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@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@research.bell-labs.com with the line: send readme Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.