Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : KRK
Date : Thu Sep 08 2005 07:27 pm

I like the idea about partitioning the space into several cubes.  You could 
do that and move recursively to smaller and smaller cubes.  I think I will 
try that.  As far as triangulation goes, I know what that is and use it with 
matlab, but I don't have time to look into it and write code, test it, 
etc... to do the triangulation for my particular problem.

I never heard of a 'Manhattan Distance'  it sounds reasonable to try.  It 
would be interesting to see how fast one could make that method, and if you 
could make it 100% accurate (I don't think so, but am not sure).  (By the 
way, I would never dream of using sqrt() to compare distances in a large 
problem, unless of course there was some reason it would be necessary for 
accuracy -- i.e. the squares were very large numbers)

One thing about this Manhattan distance.  Wouldn't it be better to use 
abs(z2-z1) + abs(y2-y1) + abs(x2-x1).  Of course you would have to code your 
own abs() function as a macro (can that be done efficiently??), or you would 
be making to many calls.


This is a nice newsgroup, lots of good responses, and quickly!


KRK

.