Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : William
Date : Fri Sep 09 2005 11:24 am

"Randy" <joe@burgershack.com> wrote in message
news:dfq18r$a0p$1@joe.rice.edu...
>
> There may be a standard answer for this, but since I don't know it, here
> goes...
>
> If you use manhattan distance (x2 - x1 + y2 - y1 + z2 - z1) instead of
> true distance sqrt(x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2), as part of a
> first pass that decides whether each point is close enough to warrant
> further consideration, you can avoid the vast majority of multiplies
> (ans sqrt calls)

Just a note: when comparing distances, you don't need the square
root, you can compare the squared distances directly. -Wm

.