Data structure for spatial data

Question

I am looking for a good functional data structure to store spatial (point) data. The data structure should allow simple epsilon queries for points already present. Also I need to modify the data quite often. This means points can move and should be able to be updated in the data structure. This can probably be handled using a normal delete/add, but a real move might be faster.

For now I am thinking about using quad/oct-trees (or higher), since the move part should be quite easy to do. However quad-trees are known to be worse as far as balancing is concerned. KD-Trees might be another choice, but the update seems quite nasty. Also most spacial data structure implementations I can find are only procedural and I am using a functional language.

Answer 1

Depending on how you are using it and quickly the points move, you might also consider sweep and prune. Basically, you keep the points sorted in one dimension (say x). If points change places very seldom, running insertion sort for every simulation step will actually be very quick.

(I think your two suggestions are already quite good, by the way)