**comp.graphics.algorithms**

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

In article <1146302922.313027.28450@i40g2000cwc.googlegroups.com>,

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.

I'm not sure I completely understand your problem, but it sounds like

the data sets are static in which case an easy algorithm is in this

paper,

A Simple Algorithm for Nearest Neighbor Search in High Dimensions

Sameer A. Nene and Shree K. Nayar

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19,

NO. 9, SEPTEMBER 1997

It can be as or sometimes more efficient than a kd tree and is MUCH

easier to code. Note that for 50 dimensions all approaches will slow

down a lot.

-- Lou Pecora (my views are my own) REMOVE THIS to email me.

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.