# comp.graphics.algorithms

## Subject: Re: nearest neighbour of a point

In article <1146317665.338373.110730@i40g2000cwc.googlegroups.com>,
"running.polygon@gmail.com" wrote:

> Even David Kinny mentioned this, but:
>
> I have gone through their approach, but the problem I think it has is
> that it filters out all points lying at some distance 'd' from the
> point under question along each of the axes. Now, it is very much
> possible to have the closest points having these co-ordinates(in
> 3-dimentions):
> A = {0.9, 0.1, 0.2}
> B = { 0.001, 0.1, 0.19}
>
> If we filter out points say even at a distance of 0.6 difference, then
> along the x-axis, the distance becomes 0.899, and the point is
> discarded from further consideration. This is what I gathered from my
> reading of the paper. I may be mistaken though. Please correct me if I
> am wrong.
>
> As an example, I took:
> >>> x=.9-.1
> >>> y=.1-.11
> >>> z=.2-.1
> >>>
> >>> x*x+y*y+z*z
> 0.65010000000000012
>
> >>> a=.6-.1
> >>> b=.7-.11
> >>> c=.5-.1
> >>> a*a+b*b+c*c
> 0.7581
>
> So, the 1st point(0.9,0.1,0.2) is closer to the point under
> question(0.1,0.11,0.1), than the 2nd one(0.6,0.7,0.5).
>

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.

-- 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 =>Re: nearest neighbour of a point =>Re: nearest neighbour of a point =>

Replies:
Re: nearest neighbour of a point

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.