Hi, And if you search for Octree on Hackage, you would have also found my Octree implementation. It does not do re-balancing, but in this type of application you talk about it may not be needed. http://hackage.haskell.org/package/Octree Funny part, is that implementation may be easier to read than algo description I read first time: http://hackage.haskell.org/package/Octree-0.5.4.2/docs/src/Data-Octree-Inter... . It worked perfectly for my use cases (checking for collisions of 1000-100000 objects), but (just in case) the initial creation from list structure make the octree balanced. Note that balanced octree is supposed to be much faster than KD-tree, and may be also faster than R-tree in memory, since it is very shallow structure - log_8 between 10k and 1m changes only from below 5 to below 7! I was also very happy with its cache behaviour, although in theory R-tree could be better. I am also extremely interested in making sure that Haskell has a good choice of multidimensional metric data structures, so I am closely following maintenance of kd-tree, Ashley´s, and Gloss´ quadtrees. And if you really want to have re-balancing, please contact me on my email. -- Best regards Michal