I'm currently toying a bit with an idea that requires me to store a potentially large amount of coordinates in memory. These coordinates can be close to each other or apart quite far. I was thinking about using a quad tree for this, but I'm not sure if that's the best way to go and if there are better approaches to this. The idea is to divide up the tree in smaller cells(like a regular quad tree) and store the accompanying objects in it. When the time comes I need to examine the direct surroundings of a stored object, I can just check out the cell(and potentially accompanying cells). I however do see a potential problem here: The amount of space required by just the quad tree could be potentially be quite large if it is static or if cells are populated densely. For a small sized area I am looking at a potential of 1 million cells alone, because searching through the cells and matching close by objects has to be fast. I am looking for ideas and solutions that can make this work quickly with the minimal amount of memory consumption. I do know that certain spots in the tree will serve as hot spots, and other spots are hardly populated. I was thinking about making the tree cells dynamic. If a cell becomes empty and it's adjacent cells are empty as well, I could have their parent delete them and when the amount of objects in child cells is below a certain threshold, merge them as well. Any other ideas?

While I haven't read into kd-trees except skimmed a bit over the Wikipedia page for a bit of background info. It appears that kd-trees are meant for 3D space partitioning, and I have no use for the Z value. All the coordinates are stored in 2D.

This is why I initially came up with a quad tree. The hot spots can be somewhat predicted before run-time but not by the software itself, and don't necessarily have to occur or can change based on time. So the welding of leafs has to be done dynamically at run-time.

If I were to go with a quad-tree, I'd go with a point quad-tree, because the locations I am storing are just X,Y coordinates. What I'm doing is a bit more related to storing geographical data, but it's not static. I'm not sure if an R-tree(R+ seems interesting here) or variants are suitable for it.

Bumping

kd trees can be used in any of "k" dimensions - hence the name [smile]