Dear All,

i'm searching for fast algorithm to find nearest point for every point

in set of points(;-) ,Euclidian space(2D or 3D), in time O(n*log(n))

or faster.

First idea i got is "Divide&Conqirer"(or "divide skin of non-killed

bear";-)

:Split set of points into 2 sets,find nearnest points and distance to

splitting line in each subset(recursively to trivial case),and for all

points with distance to line lesser than distance to nearest point

check if nearest point are in another subset.Second (bad)idea is to

sort points by "xyzxyzxyzxyz" bit mixing...

Is here another algorithms avaliable?(or where i can find more

information?)

What are faster for case when points are randomly allocated? when in

small randomly allocated groups?

Also i'm looking for similar algorithm to find intersecting lines.

Thanks in advance,

Dmytry,

http://dmytrylavrov.narod.ru