----- Mensaje original ----- De: Chris Fairles <chris.fairles@gmail.com> Fecha: Martes, Mayo 1, 2007 2:14 pm Asunto: Re: [Boost-users] [multi_index] 2D/3D range seaching Para: boost-users@lists.boost.org
Thanks for the input. I currently use kd-trees to do such range searches. Its fairly efficient, I think 2D worst case range search is around O(sqrt(N)) assuming its perfectly balanced... its slightly worse for a random tree.
Maybe theres interest in a k-D set container implemented with such a structure (although theres probably more efficient methods, kd-trees are fairly simple).
I think there'd be considerable interest in such a submission. In case you decide to roll up your sleeves and being working towards that goal, I'd recommend you take a look at Bernhard Reiter's Boost.Tree proposal: http://boost-consulting.com/vault/index.php? &direction=0&order=&directory=Containers (file tree-soc2006.zip) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html and see if your material can be fitted there. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo