Re: [Boost-users] [multi_index] 2D/3D range seaching

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2007-05-01 15:14:46

----- Mensaje original -----
De: Chris Fairles <chris.fairles_at_[hidden]>
Fecha: Martes, Mayo 1, 2007 2:14 pm
Asunto: Re: [Boost-users] [multi_index] 2D/3D range seaching
Para: boost-users_at_[hidden]

> 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