Something that I miss very much is library for multidimensional/spatial data structures.
I strongly agree with this too. I often develop libraries that are related to 3D geometry, and I always end up regretting that there doesn't exist any somehow "standard" spatial data structure that wouldn't be related to any particular implementation or product. As a consequence it's very difficult in this domain to deliver libraries that are really portable and easily integrable.
What are we talking about-- Meshes? Trees? Didn't somebody work on a half-edge mesh last summer? I personally would love it if somebody would work on interval range trees or kd trees etc. as well as meshes that work with BGL. Hopefully these can avoid the boost minefield relating to 'point' types because trees only work on coordinates (no need to intepret them as "points" per se), and meshes are entirely topological. I bet these could be two different projects. -- John Femiani