Nearest Neighbour Over Small Areas

I was recently trying to think of how to optimize a general problem, nearest neighbour search, based on specific, but probably common, conditions. Two requirements stand out. The first is that we're interested in a relatively small area, such as a city. The other is that our neighbours are constantly moving, so we have a relatively high update rate. Furthermore, while we want to be as accurate as possible, we have some leeway with respect to how perfect our results are.