Answer the question
In order to leave comments, you need to log in
Range tree in the general case, if the points have some matching coordinates?
I read this article here: goo.gl/kXmR7L and related chapters from de Berg, Computational Geometry. As the basis of the tree, it is proposed "to use a balanced binary search tree, in the leaves of which we will store the points of the desired set, and in the non-leaf vertices - the separating values that will be searched in the tree."
A one-dimensional range-tree is just the search tree described above.
d-dimensional range-tree - a search tree (by the first coordinate X_1), similar to that described above, but at each vertex additionally storing a d-1-dimensional range-tree (by the remaining coordinates X_2 x ... x X_d) for a set of elements, which are leaves of a subtree of this vertex.
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question