nearest neighbor 2 dimensions

Question

Given a set S of points in 2-dimensional space, provide an algorithm that computes nearest neighbor(euclidian) for each point in the set. I think its called nearest neighbor graph, isn't it? Any existing efficient algorithm (N log N), where N = len(S)?

Answer 1

The kd-tree is a pretty standard algorithm for nearest neighbor search (even in 2-space, don't let the first illustration throw you).