I'm looking for effective algorithm or at least possible english term to name it
for google. I have array A with set of points. I have array B with other set of
points. For each point from array A I need nearest point in array B. The
question is what structure and additional data I should use for array B to make
this finding fastest. The structure should be aplicable for any not sorted set
of points in array A.

ABX

Post a reply to this message

On Thu, 27 Feb 2003 10:19:16 +0100, ABX <abx### [at] abxartpl> wrote:
> I'm looking for effective algorithm or at least possible english term to name it
> for google.

I found it myself: http://www.google.com/search?q=Nearest+Neighbor+Search

ABX

Post a reply to this message

ABX wrote:
> I'm looking for effective algorithm or at least possible english term
> to name it for google. I have array A with set of points. I have
> array B with other set of points. For each point from array A I need
> nearest point in array B. The question is what structure and
> additional data I should use for array B to make this finding
> fastest. The structure should be aplicable for any not sorted set of
> points in array A.
>
> ABX

IMHO I would llok for a spatial subdivision structure in which store points
from B array and then perform nearest finding queries using each point in A
array. I would firstly look at:
http://www.cs.umd.edu/~brabec/quadtree/index.html
where you will find several spatial subdivision data structures (and some
useful algorithms operating with them) explained with graphical demos
implemented as java applets.
Then you can go deeper making a google search for:
octree (or the 2D variant quad-tree)
kd-tree
bsp-tree

--
Alessandro Falappa
web: http://www.falappa.net/alessandro

Post a reply to this message