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