Home Products Download Order Contacts

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.