**comp.graphics.algorithms**

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

Lou Pecora

> [...]

> After reading this I still think I don't understand your particular

> problem. But if you choose a distance d that gives you no points, you

> just increase the distance and try again. You could probably do some

> prior analysis to help guide you in choosing a good 'd' value. A kd

> tree approach will always be successful in this sense, but I found it a

> lot harder to code. You might want to check repositories like netlib

> for canned kd code.

The problem the OP points to is real. You are right that you may need

to increase d until you find some point, but a point found within a

hypercube around the target point is not necessarily nearer than a

point just outside the hypercube. To be sure of finding the nearest

point you really need to search in a hypersphere.

There are a couple of ways of doing this. One is to find the nearest

point in the hypercube, and then increase the size of the hypercube

(to side 2k where k is the distance to that point) and search again.

This ensures that any nearer point must now be inside the hypercube,

but may increase its size by a factor of sqrt(d) in the worst case.

Another way is to search specific hyperrectangles just outside the

hypercube to ensure that any nearer point is found. This way, which

is proposed in the paper by Nene and Nayar, is apparently more

efficient. They also describe how to choose suitable values of d.

David

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:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.