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,
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.
More information about the Compgeom-announce
mailing list