Adam,
I've implemented: - k-dimensional generalizations of STL containers (used by some space partitioning data structures) - k-dimensional space partitioning data structures - regular grid - kd-tree - something I've called regular tree, it's k-dimensional generalization of quadtree/octree, so for k=2 it's quadtree, for k=3 it's octree, for k=4 it's 16tree and so on. - k-dimensional euclidean algebra/geometry data structures - points, vectors etc., - unit tests.
There are boost-like names used in code allready. If you'd like to know more just ask.
I'm interested too. I might be able to contribute as I'm using space partitioning structures on an every day basis. Here are a couple of questions - what kind of split policies are implemented for the k-d tree? - how do you cope with unbalanced trees caused by dynamic insertion/deletion of points? - what queries are supported (i.e nearest neighbors, arbitrary volumes, parametric volumes) ? - do you offer incremental queries that can be stopped before evaluating the entire result set ? - did you consider to implement parallel queries ? - where's the code? Best regards, Christoph