**comp.graphics.algorithms**

## Subject: **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.

I searched on the internet & on these groups, but I didn't find

anything that can give precise answers efficiently. Almost all claim of

giving approximate answers.

However, this thread seems to be talking of just about the thing that I

want to know:

http://groups.google.co.in/group/comp.graphics.algorithms/browse_thread/thread/521eff0d732d1a29/023333825cc0584b?lnk=st&q=closest+point+in+n+dimensions&rnum=5&hl=en#023333825cc0584b

The 1st reply mentions: "Euclidean nearest neighbors in high

dimensional space. Ouch, that

hurts. Especially so if you have further knowledge about expected

input point distributions, or the number of points, N is not >> 2^k. "

However, in my case, I do have information about the expected

distribution of the input point distribution. I wonder if that could

help.

Another thing I couldn't understand from that discussion was:

"> One easy partitioning strategy that I'm exploring is by Euclidean

distance

> (or distance squared) from the origin. If this distance is more than D for

> two points then the closest those two points can be to each other is D.

As stated, that's not true. To points can both be 1 meter from the

origin and still within one millimeter of each other. The top and

bottom side of your right foot's big toe's nail achieve that easily,

with respect to your hip, as you stand.

For your conclusion to be correct, the two points' distances from the

origin have to *differ* by more than D. "

Any help would be greatly appreciated.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Replies:

Re: nearest neighbour of a point

Re: nearest neighbour of a point

Re: nearest neighbour of a point

Re: nearest neighbour of a point

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.