Newsgroups: comp.graphics Path: utzoo!utgpu!radio.astro!brian From: brian@radio.astro.utoronto.ca (Brian Glendenning) Subject: Closest pairs of points Message-ID: Sender: brian@radio.astro.utoronto.ca (Brian Glendenning) Organization: Radio Astronomy, Univeristy of Toronto Date: Tue, 14 Nov 89 21:17:38 GMT 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