**comp.graphics.algorithms**

## Subject: **Re: nearest neighbour of a point**

In <1146302922.313027.28450@i40g2000cwc.googlegroups.com> running.polygon@gmail.com writes:

> 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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

nearest neighbour of a point =>

Replies:

Re: nearest neighbour of a point

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.