orthogonal range search with rage max query

Steffen Heyne heyne at informatik.uni-freiburg.de
Mon Jan 28 12:34:51 UTC 2008


Hi,

through wikipedia I've found your implementation of an kd-tree. Thank 
you for your work!

I want to use your class for an (2D-) orthogonal range search, i.e. I 
give two 2D-points and a method should return all points within a given 
rectangle ((x1,y1),(x2,y2)). Which member I have to use for this 
purpose? "find_within_range()"?

Second question: is it possible to extend the node's data structure with 
own types and to traverse the tree nodes to manipulate these data? The 
problem I have is that I need an efficent access to the maximum within a 
given range, i.e. each point has a certain weight and a query should 
return the point with the maximum weight within a range (range max 
query) (in addition only the maximum of a certain set of "activated" 
points within a range). During the insertion of the points one have to 
update a max variable of the nodes to achieve this. Do you have any 
other ideas for a range-max query with a kd-tree?

Thanks for your help,
steffen





More information about the libkdtree-devel mailing list