Home Products Download Order Contacts

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.