Efficient Data Structure for Closest Euclidean Distance
It seems that the relevant data structure might be a dynamic Voronoi diagram.

Voronoi diagrams are often the answer when a set of points on the plane is involved.

In this case, since the point set is evolving, you want a dynamic version.