brian@radio.astro.utoronto.ca (Brian Glendenning) (11/15/89)
I don't actually want this for a graphics application, but people who code graphics applications might have done similar things in the past. Does anyone have a nice algorithm for finding the closest pairs of a set of points distributed in 2 or 3 space? That is, from the set of points (xi,yi,zi) i=1..N (say N is even), determine the pairs: (x1j,y1j,z1j; x2j,y2j,z2j) j=1..N/2 where R1 <= R2 <= R3 ... <= RN/2 where the R's are the normal euclidean separation between the points in a given pair. Each point may be a member of only one pair. The algorithms I can think up seem to be either clunky or too slow (~10^5 points). Thanks! -- Brian Glendenning - Radio astronomy, University of Toronto brian@radio.astro.utoronto.ca uunet!utai!radio!brian glendenn@utorphys.bitnet -- Brian Glendenning - Radio astronomy, University of Toronto brian@radio.astro.utoronto.ca uunet!utai!radio!brian glendenn@utorphys.bitnet
valoisj@turing.cs.rpi.edu (John Valois) (11/15/89)
In article <BRIAN.89Nov14161727@radio.astro.utoronto.ca> brian@radio.astro.utoronto.ca (Brian Glendenning) writes: > >Does anyone have a nice algorithm for finding the closest pairs of a >set of points distributed in 2 or 3 space? That is, from the set of >points (xi,yi,zi) i=1..N (say N is even), determine the pairs: > >(x1j,y1j,z1j; x2j,y2j,z2j) j=1..N/2 where R1 <= R2 <= R3 ... <= RN/2 > >where the R's are the normal euclidean separation between the points >in a given pair. > >Each point may be a member of only one pair. The algorithms I can >think up seem to be either clunky or too slow (~10^5 points). Thanks! >-- > Brian Glendenning - Radio astronomy, University of Toronto >brian@radio.astro.utoronto.ca uunet!utai!radio!brian glendenn@utorphys.bitnet Rabin [1] gives a probabilistic algorithm for which the expected number of distance computations is O(n), and which is "easily programmable". He also mentions two non-probabilistic algorithms by Shamos & Bentley [2] and Yuval [3] which require O(n log n) distance computations. [1] Rabin, M., "Probabilistic Algorithms", Algorithms and Complexity, J. F. Traub, ed., Academic Press, NY, 1976, pp. 21-39. [2] Bentley, J. and Shamos, M., "Divide-and-Conquer in Multidimensional Space", Proc. of the Eigth Annual ACM Symp. on Theory of Computing, 1976, pp. 220-230. [3] Yuval, G., "Finding Nearest Neighbours", to appear in Information Processing Letters. (sorry about the reference to Yuval's paper, that's the only information Rabin gave.) ------- John Valois valoisj@turing.cs.rpi.edu
gideony@microsoft.UUCP (Gideon Yuvall) (11/17/89)
See my paper "finding nearest neighbours", Inf. Proc. Letters 1976. -- Gideon Yuval, gideony@microsof.UUCP, 206-882-8080 (fax:206-883-8101;TWX:160520)