**comp.graphics.algorithms**

## 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

hypercube?

If so, I expect you are stuck with an O(|X| |Y| n) algorithm.

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.