Subj : To : comp.programming From : Date : Fri Sep 09 2005 03:45 pm Message-ID: <43220b14$0$1278$ed2619ec@ptn-nntp-reader02.plus.net> From: Jon Harrop Subject: Re: Locating Nearest Neighbors in space (fast) Newsgroups: comp.programming Date: Fri, 09 Sep 2005 23:19:04 +0100 References: Organization: Flying Frog Consultancy Ltd. User-Agent: KNode/0.8.2 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7Bit Lines: 29 NNTP-Posting-Host: f31bb718.ptn-nntp-reader02.plus.net X-Trace: DXC=@6b3bK3P9XL37DAj2W^2]Migd3Y`7Rb;N37XnI;[OUCDFoiLhOcW1 Does anyone know a fast algorithm to do this, preferably one that doesn't > require fancy knowledge of data structures etc since I'm not a > professional programmer. The brute force algorithm that you described is O(n^2), as you hinted. The first step to faster code is improving that asymptotic algorithmic complexity from O(n^2) to O(n log n) or even O(n). Very similar problems arise in astrophysics (simulating stars) and in condensed matter physics (simulating atoms). However, the solutions are very different because these two applications have wildly different distributions of particle separations. In astrophysics, the stars can (and often do) cluster, so the nearest neighbour distribution is very wide. In condensed matter physics, atoms tend to bustle until they are "at arms length", so the nearest neighbour distance is very sharp. If your distribution of nearest neighbour separations is heterogeneous (like stars) then I'd recommend an octree or k-D tree (adaptively subdividing space). If your distribution of nearest neighbour separations is very sharp (like atoms in a solid) then I'd recommend voxels (uniformly dividing space up into cubes). You can do voxels easily enough in C/C++ but if you're going to use trees then I'd recommend switching to a more modern language, like OCaml or SML. -- Dr Jon D Harrop, Flying Frog Consultancy http://www.ffconsultancy.com .