Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!gem.mps.ohio-state.edu!rpi!turing.cs.rpi.edu!valoisj From: valoisj@turing.cs.rpi.edu (John Valois) Newsgroups: comp.graphics Subject: Re: Closest pairs of points Message-ID: <1989Nov15.155237.25938@rpi.edu> Date: 15 Nov 89 15:52:37 GMT References: Reply-To: valoisj@turing.cs.rpi.edu (John Valois) Organization: RPI CS Dept. Lines: 37 In article 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