I am in need of an algorithm for a part of a game (a mod) I am making. I have abstracted the problem:Given a 2D space with $N$ random points $p_1...p_n$, calculate the nearest neighbor of each of the points, where the distance is at most $C$.Note that our list of points is unsorted, and that each point is an actual object so I could give it any property I want.Now this can easily be done in $O(n^2)$ time, it is also the easiest and not really an issue.However, the time it takes when a new point is added or a point is removed is also $O(n^2)$, and I would like to get that down, because this is done during gameplay (while the initial step is only done at start).Does anyone know a possible improvement over the simple 'bruteforce'? I tried sorting, twice, and keeping it up to date (using a 4x linked list (up, down, left, right)) but that did not seem to work.
All nearest neighbor in a changing 2d euclidean space
algorithms;nearest neighbour;euclidean distance
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.