<div dir="ltr"><div dir="ltr" style="font-size:12.8000001907349px">Hi,<div><br></div><div>And if you search for Octree on Hackage, you would have also found my Octree implementation.<div>It does not do re-balancing, but in this type of application you talk about it may not be needed.</div><div><a href="http://hackage.haskell.org/package/Octree" target="_blank">http://hackage.haskell.org/package/Octree</a><br></div><div><br></div><div>Funny part, is that implementation may be easier to read than algo description I read first time:<br></div><div><a href="http://hackage.haskell.org/package/Octree-0.5.4.2/docs/src/Data-Octree-Internal.html" target="_blank">http://hackage.haskell.org/package/Octree-0.5.4.2/docs/src/Data-Octree-Internal.html</a>.</div><div><br></div><div>It worked perfectly for my use cases (checking for collisions of 1000-100000 objects),</div><div>but (just in case) the initial creation from list structure make the octree balanced.</div><div>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!</div><div>I was also very happy with its cache behaviour, although in theory R-tree could be better.</div><div><br></div><div>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.</div><div>And if you really want to have re-balancing, please contact me on my email.</div><div>--</div><div>  Best regards</div><div>    Michal</div></div></div>
</div>