Home Products Download Order Contacts


Subject: Re: nearest neighbour of a point

running.polygon@gmail.com wrote:
> 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.

This one is still unclear on how X and Y were obtained.

I gather that X and Y are subsets of unit hypercube [0,1]^n,
where n is an integer that might be as large as 50.
Are the elements of X and Y drawn uniformly at random from the
If so, I expect you are stuck with an O(|X| |Y| n) algorithm.


View All Messages in comp.graphics.algorithms

nearest neighbour of a point =>

Re: nearest neighbour of a point

Copyright 2006 WatermarkFactory.com. All Rights Reserved.