All nearest neighbor in a changing 2d euclidean space
You want a data structure that supports nearest neighbor search in 2D.  There are many options, but a simple one that is widely used for practical situations is a quadtree data structure.  It supports both efficient lookup and efficient insert operations.