**comp.graphics.algorithms**

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

In comp.graphics.algorithms running.... wrote:

> All the points lie within a hypercube of side 1 and all points are

> having non-negative co-ordinates in each of the dimensions. So, if we

> consider 3D, then they would all lie in a cube of side 1 in the 1st

> octant(if that's what it's called).

So, to reduce the words to a concise formula: your input sets are

contained in [0:1]^N, for N somewhere around 20, possibly up to 50.

> and the number of points having dist^ between 10 & 11 would probably be

> the most.

You'ld better verify that probability. The actual expected distance

is 0.5 in each coordinate, which ends up as an expected squared

distance of 20*(0.25). I.e. the average squared distance would be 5,

not 10.

But that doesn't really help you anything. Uniform distribution in an

N-dimensional hypercube is the worst case for nearest-neighbor

searches. If your points don't cluster in any known way inside that

hypercube, the naive O(|X|*|Y|) algorithm will be unbeatable.

To repeat:

> > The fact to remember is that in

> > high-dimensional spaces, everything is pretty much next to everything

> > else, so the only way to find the closest thing is to check

> > everything.

> However, instead of considering the thickness of the hyperspherical

> shell to be the width of the distribution, we let the thickness be say

> the standard deviation of the distribution,

That is what I meant by "width".

> Let y be a point in set Y, and let dy be the dist^2 of y from {0,0,0}.

> Say that I have a list of all points in set X such that they are sorted

> in ascending order on their dist^2 from {0,0,0}.

> Now, I can say that the point in set X which is closest to point y is

> one which lies in the band such that the band contains all points at a

> distance of [dy-DELTA] to [dy+DELTA] such that DELTA is chosen in such

> a way that it encompases at least the point which is closest to y.

And the problem with that is that DELTA will be too large.

In a nutshell: sorting doesn't preserve distance in spaces of

dimension greater than one.

--

Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)

Even if all the snow were burnt, ashes would remain.

Reply

View All Messages in

**comp.graphics.algorithms**

path:

nearest neighbour of a point =>Re: nearest neighbour of a point =>Re: nearest neighbour of a point =>Re: nearest neighbour of a point =>

Replies:

Re: nearest neighbour of a point

Re: nearest neighbour of a point

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.