Re: Locating Nearest Neighbors in space (fast)

KRK wrote:
> 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
.

Relevant Pages

  • Re: Big Push for Guest Worker Program
    ... so that I wouldn't every have to do taxes again. ... Since my big distribution comes in November, ... I remember my car license plate ID by an algorithm rather ...
    (soc.retirement)
  • Re: GetHashCode for Objects that Compare Based on Value (Not reference equality)
    ... Further, for those sets of data, an XOR hash produces a sufficiently ... random distribution for hashes to work just fine. ... realm of developing a good generic algorithm; ... Saying that XOR produces collisions is not very useful. ...
    (microsoft.public.dotnet.framework)
  • Re: GetHashCode for Objects that Compare Based on Value (Not reference equality)
    ... one cannot characterize 'all data' or even 'real life ... my algorithm you quickly get a broader range. ... the definition of random distribution, and thus should data in member ... It follows that given a class with random member variable values, ...
    (microsoft.public.dotnet.framework)
  • Re: erf function in C
    ... Would you still recommend this? ... Is there another fast but portable algorithm with sufficient ... > should serve very well for solving the equation ... the Taylor series was easy and fast only for the first few ...
    (comp.lang.c)
  • Re: Prime numbers
    ... The prime numbers are produced by the algorithm of the Eratosthenes ... That algorithm is equivalent to a Pseudorandom Generator. ... distribution known as the Gauss Distribution. ... "Une des hypotheses les plus interesantes auxquelles conduisent les ...
    (sci.math)