Subj : Re: Locating Nearest Neighbors in space (fast) To : comp.programming From : Tim Menzies Date : Thu Sep 08 2005 02:50 pm In article , Arthur J. O'Dwyer wrote: > > On Thu, 8 Sep 2005, KRK wrote: >> >> I'm programming in C > [...] >> Position *array1; /*Approx. 50,000 Entries*/ >> Position *array2; /*Approx 50,000 Entries*/ >> >> My problem is this, I want to take each point in array 1, and find its >> 'nearest spatial neighbor' in array 2. This can be done by brute force, but >> is rather slow, since to do this requires on the order of 10^10 multiplies. >> Further, I want to do this operation abot 180 times! > > (With different sets of points, I assume!) > The first thing I thought of was "partitioning." Divide space into a > bunch of cubes, and for each cube, get the set of points located inside > that cube. Then for a point P in cube C, the nearest neighbor of P will > either be inside cube C, or inside one of the 26 neighbors of C,[1] unless > all 27 of those cubes are empty, in which case you'll need to look at > the 98 cubes next to the neighbors of C, and so on. (At some point, if P > is really lonely out there, you can just revert to brute force.) i think you want "ball trees". see http://citeseer.ist.psu.edu/nrelatedgid/273722 t ----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups ----= East and West-Coast Server Farms - Total Privacy via Encryption =---- .