All nearest neighbor in a changing 2d euclidean space

Question

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.