# comp.graphics.algorithms

## Subject: Re: nearest neighbour of a point

> I have 2 sets of points X & Y. The distribution of points in both the
> sets is such that points at a certain distance are concentrated and on
> either side of this distance, they start becoming sparce, something
> like a normal distribution. The points are in higher dimentions > 3.
> They may be up to 50 dimentions. Now, there are many points in each of
> the sets, and I would like to know if there is any efficient method to
> find for each point in set Y, a point in set X such that the distance
> between the point in set Y & the selected point in set X is <= the
> distance between the point in set Y and any other point in set X. I can
> use euclidean distance as the metric.

> I'm mainly interested in finding a way of efficiently eliminating as
> many bogus points(those which are surely not at the least distance)
> from set X for each point in set Y, and I don't mind applying eucledian
> distance on a handful of points, say 1000 per point in set Y.

> [...]

If your data is largely static you may find this approach works:

http://citeseer.ifi.unizh.ch/cache/papers/cs/17050/ftp:zSzzSzftp.cs.columbia.eduzSzpubzSzsameerzSzsearch.pdf/nene97simple.pdf

HTH,
David