Karl, your idea is not that far fetched. The problem with loose structures, such as an ABT, is that there is no direct hierarchical relationship between spatially close nodes. Nodes can practically be in arbitrary positions, two hierarchically close branches don''t have to be spatially near. The opposite is also true: two spatially close nodes don''t have to be hierarchically related in any way. In fact, they could be at opposite sides of the tree !

So, you definitely need a separate structure representing purely spatial relationships, independent of the hierarchy itself. The concept Karl mentioned is basically a kind of PVS for ABT nodes, let''s called it a ''potential neighbour set''. Note the term ''potential'': since ABTs do not have guaranteed neighbours, such a structure could only hold an approximation. But that''s perhaps all you need. For every side of a node (+x, +y, +z, -x, -y, -z) keep a linked list of pointers to other nodes that are potentially close to the respective side of the node. When moving a dynamic object through the tree (growing nodes as needed), this structure would help tremendeously in determining new candidate insertion points for the object. Assuming the tree becomes too denormalized, then instead of rebuilding the whole denormalized branch, you could simply ''snap it back''. The dynamic object would then ''float'', ie. it would be unassigned. Using the potential neighbour sets of the old parent node, you would then perform a local restricted search through the set, trying to get the best fit node for reinsertion of the dynamic object.

Such an ABT extension would certainly work. But the main problems I see with that approach are memory consumption (the potential neighbour lists can quickly get overwhelming in terms of size) and search speed (in very deep branches with tons of spatially near nodes). And most important of all, keeping the structure up-to-date as the tree moves/deforms, at interactive rates, is going to be a major challenge.