In the original article on R+ tree, Algorithm Insert recursively searches for all leaf nodes that overlap the given input rectangle IR and adds IR to each of those leaves. But what if part of IR is not covered by any existing leaf? How will that part ever be indexed?

  • $\begingroup$ I assume you just enlarge the rectangles associated with each node on the path of these leafs to the root, so that they cover the new rectangles completely. I think there are various heuristics in splitting leafs and redistributing rectangles to try and counter this. Thats the nice thing about R^*+/--trees - they dont panic if there is some overlap. $\endgroup$ – Sariel Har-Peled Mar 7 '11 at 2:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy