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