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))
First idea i got is "Divide&Conqirer"(or "divide skin of non-killed
: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
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,